{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Avoid Flood in The City"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #hash-table #binary-search #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #哈希表 #二分查找 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: avoidFlood"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #避免洪水泛滥"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你的国家有无数个湖泊，所有湖泊一开始都是空的。当第 <code>n</code>&nbsp;个湖泊下雨前是空的，那么它就会装满水。如果第 <code>n</code>&nbsp;个湖泊下雨前是 <strong>满的&nbsp;</strong>，这个湖泊会发生 <strong>洪水</strong> 。你的目标是避免任意一个湖泊发生洪水。</p>\n",
    "\n",
    "<p>给你一个整数数组&nbsp;<code>rains</code>&nbsp;，其中：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>rains[i] &gt; 0</code>&nbsp;表示第 <code>i</code>&nbsp;天时，第 <code>rains[i]</code>&nbsp;个湖泊会下雨。</li>\n",
    "\t<li><code>rains[i] == 0</code>&nbsp;表示第 <code>i</code>&nbsp;天没有湖泊会下雨，你可以选择 <strong>一个</strong>&nbsp;湖泊并 <strong>抽干</strong>&nbsp;这个湖泊的水。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请返回一个数组<em>&nbsp;</em><code>ans</code>&nbsp;，满足：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>ans.length == rains.length</code></li>\n",
    "\t<li>如果&nbsp;<code>rains[i] &gt; 0</code> ，那么<code>ans[i] == -1</code>&nbsp;。</li>\n",
    "\t<li>如果&nbsp;<code>rains[i] == 0</code>&nbsp;，<code>ans[i]</code>&nbsp;是你第&nbsp;<code>i</code>&nbsp;天选择抽干的湖泊。</li>\n",
    "</ul>\n",
    "\n",
    "<p>如果有多种可行解，请返回它们中的 <strong>任意一个</strong>&nbsp;。如果没办法阻止洪水，请返回一个 <strong>空的数组</strong>&nbsp;。</p>\n",
    "\n",
    "<p>请注意，如果你选择抽干一个装满水的湖泊，它会变成一个空的湖泊。但如果你选择抽干一个空的湖泊，那么将无事发生。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>rains = [1,2,3,4]\n",
    "<strong>输出：</strong>[-1,-1,-1,-1]\n",
    "<strong>解释：</strong>第一天后，装满水的湖泊包括 [1]\n",
    "第二天后，装满水的湖泊包括 [1,2]\n",
    "第三天后，装满水的湖泊包括 [1,2,3]\n",
    "第四天后，装满水的湖泊包括 [1,2,3,4]\n",
    "没有哪一天你可以抽干任何湖泊的水，也没有湖泊会发生洪水。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>rains = [1,2,0,0,2,1]\n",
    "<strong>输出：</strong>[-1,-1,2,1,-1,-1]\n",
    "<strong>解释：</strong>第一天后，装满水的湖泊包括 [1]\n",
    "第二天后，装满水的湖泊包括 [1,2]\n",
    "第三天后，我们抽干湖泊 2 。所以剩下装满水的湖泊包括 [1]\n",
    "第四天后，我们抽干湖泊 1 。所以暂时没有装满水的湖泊了。\n",
    "第五天后，装满水的湖泊包括 [2]。\n",
    "第六天后，装满水的湖泊包括 [1,2]。\n",
    "可以看出，这个方案下不会有洪水发生。同时， [-1,-1,1,2,-1,-1] 也是另一个可行的没有洪水的方案。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>rains = [1,2,0,1,2]\n",
    "<strong>输出：</strong>[]\n",
    "<strong>解释：</strong>第二天后，装满水的湖泊包括 [1,2]。我们可以在第三天抽干一个湖泊的水。\n",
    "但第三天后，湖泊 1 和 2 都会再次下雨，所以不管我们第三天抽干哪个湖泊的水，另一个湖泊都会发生洪水。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= rains.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= rains[i] &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [avoid-flood-in-the-city](https://leetcode.cn/problems/avoid-flood-in-the-city/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [avoid-flood-in-the-city](https://leetcode.cn/problems/avoid-flood-in-the-city/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,4]', '[1,2,0,0,2,1]', '[1,2,0,1,2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def avoidFlood(self, rains: List[int]) -> List[int]:\n",
    "        #解题思路：\n",
    "        #需要一个字典存储当前有水的湖泊，及哪天下的雨\n",
    "        #对于不下雨的天，如果有水的湖泊数=1，直接对这个湖泊操作；=0不操作；>1，待判断操作哪一个\n",
    "        #一个数组来存储待判断的天数。遇到情况时直接操作即可\n",
    "\n",
    "        if len(rains) == 1:\n",
    "            return [-1]\n",
    "\n",
    "        dict_ = {} #水池：下雨天\n",
    "        list_ = []\n",
    "        res = [-1] * len(rains)\n",
    "        for i in range(len(rains)):\n",
    "            if rains[i] == 0: #如果当天不下雨\n",
    "                if len(dict_) == 1:\n",
    "                    res[i] = list(dict_.keys())[0]\n",
    "                    dict_.clear()\n",
    "                else: #多个水池为满\n",
    "                    res[i] = 1\n",
    "                    list_.append(i)\n",
    "                    list_.sort()\n",
    "            else:\n",
    "                res[i] = -1\n",
    "                if rains[i] not in dict_: #如果j湖泊为空\n",
    "                    dict_[rains[i]] = i\n",
    "                elif not list_ or (list_ and dict_[rains[i]] > list_[-1]): #如果湖泊装满水之后没有晴天\n",
    "                    return []\n",
    "                else:\n",
    "                    j = 0\n",
    "                    while list_[j] < dict_[rains[i]]:\n",
    "                        j += 1\n",
    "                    res[list_.pop(j)] = rains[i]\n",
    "                    dict_[rains[i]] = i\n",
    "       \n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def avoidFlood(self, rains: List[int]) -> List[int]:\n",
    "        l=len(rains)\n",
    "        r=[-1 for _ in range(l)]\n",
    "        dupool=list()\n",
    "        s=set()\n",
    "        \n",
    "        for i in range(l):\n",
    "            if not rains[i]:\n",
    "                r[i]=1\n",
    "                continue\n",
    "            \n",
    "            if rains[i] not in s:\n",
    "                s.add(rains[i])\n",
    "            else:\n",
    "                dupool.append(rains[i])\n",
    "        \n",
    "        s=set()\n",
    "        for i in range(l):\n",
    "            if not rains[i]:\n",
    "                for k in range(len(dupool)):\n",
    "                    t=dupool[k]\n",
    "                    if t in s:\n",
    "                        r[i] = t\n",
    "                        s.remove(t)\n",
    "                        dupool.pop(k)\n",
    "                        break\n",
    "            else:\n",
    "                if rains[i] not in s:\n",
    "                    s.add(rains[i])\n",
    "                else:\n",
    "                    return []\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def avoidFlood(self, rains: List[int]) -> List[int]:\n",
    "        dic = defaultdict(int)\n",
    "        turns = 0\n",
    "        delete_list,res = [],[]\n",
    "        for item in rains:\n",
    "            # print(item)\n",
    "            if item ==0:\n",
    "                turns +=1\n",
    "            else:\n",
    "                if dic[item]!=0:\n",
    "                    print(item)\n",
    "                    if turns ==0:\n",
    "                        return []\n",
    "                    else:\n",
    "                        turns -= 1\n",
    "                        delete_list.append(item)\n",
    "                        # dic[item] = 0\n",
    "                else:\n",
    "                    dic[item]=1\n",
    "        # print('first ok')\n",
    "        # print(delete_list)\n",
    "        # print(dic)\n",
    "        dic = defaultdict(int)\n",
    "        i = 0\n",
    "        for item in rains:\n",
    "            # print(res)\n",
    "            if item > 0:\n",
    "                res.append(-1)\n",
    "                if dic[item]>0:\n",
    "                    return []\n",
    "                else:\n",
    "                    dic[item] = 1\n",
    "            else:\n",
    "                i,flag = 0,False\n",
    "                for i in range(len(delete_list)):\n",
    "                    if dic[delete_list[i]] > 0:\n",
    "                        flag = True\n",
    "                        dic[delete_list[i]] = 0\n",
    "                        res.append(delete_list[i])\n",
    "                        break\n",
    "                if flag:\n",
    "                    delete_list = delete_list[0:i]+delete_list[i+1:]\n",
    "                else:\n",
    "                    res.append(1)\n",
    "        return res\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def avoidFlood(self, rains: List[int]) -> List[int]:\n",
    "        dic = defaultdict(int)\n",
    "        turns = 0\n",
    "        delete_list,res = [],[]\n",
    "        for item in rains:\n",
    "            print(item)\n",
    "            if item ==0:\n",
    "                turns +=1\n",
    "            else:\n",
    "                if dic[item]!=0:\n",
    "                    print(item)\n",
    "                    if turns ==0:\n",
    "                        return []\n",
    "                    else:\n",
    "                        turns -= 1\n",
    "                        delete_list.append(item)\n",
    "                        # dic[item] = 0\n",
    "                else:\n",
    "                    dic[item]=1\n",
    "        print('first ok')\n",
    "        print(delete_list)\n",
    "        print(dic)\n",
    "        dic = defaultdict(int)\n",
    "        i = 0\n",
    "        for item in rains:\n",
    "            # print(res)\n",
    "            if item > 0:\n",
    "                res.append(-1)\n",
    "                if dic[item]>0:\n",
    "                    return []\n",
    "                else:\n",
    "                    dic[item] = 1\n",
    "            else:\n",
    "                i,flag = 0,False\n",
    "                for i in range(len(delete_list)):\n",
    "                    if dic[delete_list[i]] > 0:\n",
    "                        flag = True\n",
    "                        dic[delete_list[i]] = 0\n",
    "                        res.append(delete_list[i])\n",
    "                        break\n",
    "                if flag:\n",
    "                    delete_list = delete_list[0:i]+delete_list[i+1:]\n",
    "                else:\n",
    "                    res.append(1)\n",
    "        return res\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def avoidFlood(self, rains: List[int]) -> List[int]:\n",
    "        n = len(rains)\n",
    "        res = [1] * n\n",
    "        tmp = {}\n",
    "        flag = []\n",
    "        for i, val in enumerate(rains):\n",
    "            if val > 0:\n",
    "                if val in tmp:\n",
    "                    idx = bisect.bisect_left(flag, tmp[val])\n",
    "                    if idx == len(flag):\n",
    "                        return []\n",
    "                    else:\n",
    "                        j = flag.pop(idx)\n",
    "                        res[j] = val\n",
    "                tmp[val] = i \n",
    "                res[i] = -1\n",
    "            else:\n",
    "                flag.append(i)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def avoidFlood(self, rains: List[int]) -> List[int]:\n",
    "        n = len(rains)\n",
    "        res = [1] * n\n",
    "        tmp = {}\n",
    "        flag = []\n",
    "        for i, val in enumerate(rains):\n",
    "            if val > 0:\n",
    "                if val not in tmp:\n",
    "                    res[i] = -1\n",
    "                    tmp[val] = i \n",
    "                else:\n",
    "                    idx = bisect.bisect_left(flag, tmp[val])\n",
    "                    if idx == len(flag):\n",
    "                        return []\n",
    "                    else:\n",
    "                        j = flag.pop(idx)\n",
    "                        res[j] = val\n",
    "                        tmp[val] = i \n",
    "                        res[i] = -1\n",
    "            else:\n",
    "                flag.append(i)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def avoidFlood(self, rains: List[int]) -> List[int]:\n",
    "        n = len(rains)\n",
    "        dry = []\n",
    "        ans = [1]*n\n",
    "        water = {}\n",
    "\n",
    "        def bisect(waterIndex):\n",
    "            m = len(dry)\n",
    "            i, j = 0, m-1\n",
    "            while i<=j:\n",
    "                mid = (i+j)//2\n",
    "                if dry[mid] > waterIndex:\n",
    "                    j = mid - 1\n",
    "                elif dry[mid] < waterIndex:\n",
    "                    i = mid + 1\n",
    "            return i\n",
    "\n",
    "        for i, rain in enumerate(rains):\n",
    "            if rain==0:\n",
    "                dry.append(i)\n",
    "            else:\n",
    "                ans[i] = -1\n",
    "                if rain in water:\n",
    "                    index = bisect(water[rain])\n",
    "                    if index == len(dry):\n",
    "                        return []\n",
    "                    ans[ dry[index] ] = rain \n",
    "                    dry.pop(index)\n",
    "                water[rain] = i \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def avoidFlood(self, rains: List[int]) -> List[int]:\n",
    "        n = len(rains)\n",
    "        ans = [1]*n\n",
    "        st = []#存储可抽水的index\n",
    "        mp = {}\n",
    "        def bisect(st, poolIndex):\n",
    "            #找到第一个大于poolIndex的可抽水index\n",
    "            m = len(st)\n",
    "            i, j = 0, m-1\n",
    "            mid = (i+j)//2\n",
    "            while i<=j: \n",
    "                mid = (i+j)//2\n",
    "                if st[mid] < poolIndex:\n",
    "                    i = mid + 1\n",
    "                elif st[mid] > poolIndex:\n",
    "                    j = mid-1\n",
    "            return j+1\n",
    "\n",
    "        for i, pool in enumerate(rains):\n",
    "            if pool == 0:\n",
    "                st.append(i)\n",
    "            else:\n",
    "                ans[i] = -1\n",
    "                if pool in mp: #第二次下雨\n",
    "                    # it = st.bisect(mp[pool])\n",
    "                    it = bisect(st, mp[pool])\n",
    "                    if it == len(st):\n",
    "                        return []\n",
    "                    ans[ st[it] ]  = pool\n",
    "                    st.remove(st[it])\n",
    "                mp[pool] = i \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def avoidFlood(self, rains: List[int]) -> List[int]:\n",
    "        fulled = {}\n",
    "        n = len(rains)\n",
    "        res = [-1] * n\n",
    "        #queue = []\n",
    "        queue = SortedList()#插入删除为 O(log n)\n",
    "        for i,num in enumerate(rains):\n",
    "            if num == 0:\n",
    "                #queue.append(i)\n",
    "                queue.add(i)\n",
    "            elif num not in fulled:\n",
    "                #fulled.add(num)\n",
    "                fulled[num]=i\n",
    "            else:\n",
    "                if not queue: return []\n",
    "                l,r = 0,len(queue)\n",
    "                while l<r:\n",
    "                    m = (l+r)//2\n",
    "                    if queue[m]<fulled[num]:\n",
    "                        l=m+1\n",
    "                    else:\n",
    "                        r=m\n",
    "                if l<len(queue):\n",
    "                    res[queue[l]] = num\n",
    "                    fulled[num]=i\n",
    "                    #queue.pop(l)\n",
    "                    queue.discard(queue[l])\n",
    "                else:\n",
    "                    return []\n",
    "                '''\n",
    "                find_flag = False\n",
    "                for j in range(len(queue)):\n",
    "                    if queue[j]>=fulled[num]:\n",
    "                        res[queue[j]] = num\n",
    "                        fulled[num]=i\n",
    "                        queue.pop(j)\n",
    "                        find_flag = True\n",
    "                        break\n",
    "                if not find_flag:\n",
    "                    return []\n",
    "                '''\n",
    "            #print(i,num,queue,fulled)\n",
    "        while queue:\n",
    "            res[queue.pop(0)] = 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def avoidFlood(self, rains: List[int]) -> List[int]:\n",
    "        fulled = {}\n",
    "        n = len(rains)\n",
    "        res = [-1] * n\n",
    "        #queue = []\n",
    "        queue = SortedList()\n",
    "        for i,num in enumerate(rains):\n",
    "            if num == 0:\n",
    "                #queue.append(i)\n",
    "                queue.add(i)\n",
    "            elif num not in fulled:\n",
    "                #fulled.add(num)\n",
    "                fulled[num]=i\n",
    "            else:\n",
    "                if not queue: return []\n",
    "                l,r = 0,len(queue)\n",
    "                while l<r:\n",
    "                    m = (l+r)//2\n",
    "                    if queue[m]<fulled[num]:\n",
    "                        l=m+1\n",
    "                    else:\n",
    "                        r=m\n",
    "                if l<len(queue):\n",
    "                    res[queue[l]] = num\n",
    "                    fulled[num]=i\n",
    "                    #queue.pop(l)\n",
    "                    queue.discard(queue[l])\n",
    "                else:\n",
    "                    return []\n",
    "                '''\n",
    "                find_flag = False\n",
    "                for j in range(len(queue)):\n",
    "                    if queue[j]>=fulled[num]:\n",
    "                        res[queue[j]] = num\n",
    "                        fulled[num]=i\n",
    "                        queue.pop(j)\n",
    "                        find_flag = True\n",
    "                        break\n",
    "                if not find_flag:\n",
    "                    return []\n",
    "                '''\n",
    "            #print(i,num,queue,fulled)\n",
    "        while queue:\n",
    "            res[queue.pop(0)] = 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def avoidFlood(self, rains: List[int]) -> List[int]:\n",
    "        n=len(rains)\n",
    "        full=dict()\n",
    "        empty=[]\n",
    "        L=[-1]*n\n",
    "        \n",
    "        l=[]\n",
    "\n",
    "        for i in range(n):\n",
    "            if rains[i]!=0:\n",
    "                if  rains[i] not in full.keys():\n",
    "                    full[rains[i]]=i\n",
    "                    \n",
    "                else:\n",
    "                    flag=0\n",
    "                    for j in empty:\n",
    "                        print(\"比较：\",i,full[rains[i]],j)\n",
    "                        if j>full[rains[i]]:\n",
    "                            full.pop(rains[i])\n",
    "                            empty.remove(j)\n",
    "                            l.append([j,rains[i]])\n",
    "                            flag=1\n",
    "                            full[rains[i]]=i\n",
    "                            break\n",
    "                            # print(\"头删\",empty.pop(0))\n",
    "                    if flag==0:\n",
    "                        return []\n",
    "            else:\n",
    "                empty.append(i) \n",
    "        \n",
    "        for i in l:\n",
    "            L[i[0]]=i[1] \n",
    "        for i in empty:\n",
    "            L[i]=1\n",
    "        return L"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def avoidFlood(self, rains: List[int]) -> List[int]:\n",
    "        n = len(rains)\n",
    "        ans = []\n",
    "\n",
    "        # 跟踪湖泊变满的那一天，key：value = 湖泊编号：变满的那天\n",
    "        fulllakes = {}\n",
    "\n",
    "        # 跟踪可以抽水的日子\n",
    "        drydays = set() \n",
    "\n",
    "        for i in range(n):\n",
    "            if rains[i] == 0:\n",
    "                drydays.add(i)\n",
    "                ans.append(1) # 暂时加入 1 ，可以被覆盖\n",
    "            else:    # 下雨\n",
    "                lake = rains[i]   # 这一天 ，lake 要下雨了\n",
    "                if lake in fulllakes:    # 如果它之前已经满了\n",
    "                    dryday = next((day for day in drydays if day > fulllakes[lake]), None)\n",
    "                    if not dryday:\n",
    "                        return []    # 没有可以抽水的日子\n",
    "                    ans[dryday] = lake \n",
    "                    drydays.remove(dryday) \n",
    "                # 更新该湖泊在哪一天变满\n",
    "                fulllakes[lake] = i \n",
    "                ans.append(-1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def avoidFlood(self, rains: List[int]) -> List[int]:\n",
    "        # n = len(rains)\n",
    "        # res = [1 for _ in range(n)]\n",
    "        # sunny = SortedList()\n",
    "        # rainy = dict()\n",
    "        # for i, x in enumerate(rains) :\n",
    "        #     if x :\n",
    "        #         res[i] = -1\n",
    "        #         if x in rainy :\n",
    "        #             idx = sunny.bisect_right(rainy[x])\n",
    "        #             if idx == len(sunny) :\n",
    "        #                 return []\n",
    "        #             res[sunny[idx]] = x\n",
    "        #             sunny.remove(sunny[idx])\n",
    "        #         rainy[x] = i\n",
    "        #     else :\n",
    "        #         sunny.add(i)\n",
    "\n",
    "        # return res\n",
    "\n",
    "\n",
    "        # n = len(rains)\n",
    "        # res = [1 for _ in range(n)]\n",
    "        # rainy = dict()\n",
    "        # pa = list(range(n + 1))\n",
    "        # def find(x):\n",
    "        #     if pa[x] != x:\n",
    "        #         pa[x] = find(pa[x])\n",
    "        #     return pa[x]\n",
    "        # # def union(x):\n",
    "        # #     pa[find(x)] = find(x + 1)\n",
    "        \n",
    "        # for i, x in enumerate(rains) :\n",
    "        #     if x :\n",
    "        #         res[i] = -1\n",
    "        #         if x in rainy :\n",
    "        #             idx = find(rainy[x])\n",
    "        #             if idx == i :\n",
    "        #                 return []\n",
    "        #             res[idx] = x\n",
    "        #             pa[idx] = idx + 1\n",
    "        #             # union(idx)\n",
    "        #         rainy[x] = i\n",
    "        #         pa[i] = i + 1\n",
    "        #         # union(i)\n",
    "        # return res\n",
    "                    \n",
    "\n",
    "        # next_rain = [-1]*len(rains)\n",
    "        # rain_dict = {}\n",
    "        # for i in reversed(range(len(rains))):\n",
    "        #     if rains[i]:\n",
    "        #         if rains[i] in rain_dict:\n",
    "        #             next_rain[i] = rain_dict[rains[i]]\n",
    "        #         rain_dict[rains[i]] = i\n",
    "        # danger = []\n",
    "        # ret = []\n",
    "        # immediate_danger = 0\n",
    "        # for i, lake in enumerate(rains):\n",
    "        #     if lake > 0:\n",
    "        #         if lake == immediate_danger:\n",
    "        #             return []\n",
    "        #         ret.append(-1)\n",
    "        #         if next_rain[i]!=-1:\n",
    "        #             heapq.heappush(danger, (next_rain[i], lake))\n",
    "        #             immediate_danger = danger[0][1]\n",
    "        #     elif danger:\n",
    "        #         target = heapq.heappop(danger)\n",
    "        #         ret.append(target[1])\n",
    "        #         if danger:\n",
    "        #             immediate_danger = danger[0][1]\n",
    "        #         else:\n",
    "        #             immediate_danger = 0\n",
    "        #     else:\n",
    "        #         ret.append(1)\n",
    "        # return ret\n",
    "\n",
    "        n = len(rains)\n",
    "        next_rain = [-1 for _ in range(n)]\n",
    "        rainy = dict()\n",
    "        for i in range(n - 1, -1, -1) :\n",
    "            if (x := rains[i]) :\n",
    "                next_rain[i] = rainy.get(x, -1)\n",
    "                rainy[x] = i\n",
    "        lakes = []\n",
    "        res = []\n",
    "        # danger = 0\n",
    "        for i, x in enumerate(rains) :\n",
    "            if x :\n",
    "                if lakes and x == lakes[0][1] :\n",
    "                    return []\n",
    "                res.append(-1)\n",
    "                if next_rain[i] != -1 :\n",
    "                    heapq.heappush(lakes, (next_rain[i], x))\n",
    "            elif lakes :\n",
    "                res.append(heapq.heappop(lakes)[1])\n",
    "            else :\n",
    "                res.append(1)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def avoidFlood(self, rains: List[int]) -> List[int]:\n",
    "        # n = len(rains)\n",
    "        # res = [1 for _ in range(n)]\n",
    "        # sunny = SortedList()\n",
    "        # rainy = dict()\n",
    "        # for i, x in enumerate(rains) :\n",
    "        #     if x :\n",
    "        #         res[i] = -1\n",
    "        #         if x in rainy :\n",
    "        #             idx = sunny.bisect_right(rainy[x])\n",
    "        #             if idx == len(sunny) :\n",
    "        #                 return []\n",
    "        #             res[sunny[idx]] = x\n",
    "        #             sunny.remove(sunny[idx])\n",
    "        #         rainy[x] = i\n",
    "        #     else :\n",
    "        #         sunny.add(i)\n",
    "\n",
    "        # return res\n",
    "\n",
    "\n",
    "        # n = len(rains)\n",
    "        # res = [1 for _ in range(n)]\n",
    "        # rainy = dict()\n",
    "        # pa = list(range(n + 1))\n",
    "        # def find(x):\n",
    "        #     if pa[x] != x:\n",
    "        #         pa[x] = find(pa[x])\n",
    "        #     return pa[x]\n",
    "        # # def union(x):\n",
    "        # #     pa[find(x)] = find(x + 1)\n",
    "        \n",
    "        # for i, x in enumerate(rains) :\n",
    "        #     if x :\n",
    "        #         res[i] = -1\n",
    "        #         if x in rainy :\n",
    "        #             idx = find(rainy[x])\n",
    "        #             if idx == i :\n",
    "        #                 return []\n",
    "        #             res[idx] = x\n",
    "        #             pa[idx] = idx + 1\n",
    "        #             # union(idx)\n",
    "        #         rainy[x] = i\n",
    "        #         pa[i] = i + 1\n",
    "        #         # union(i)\n",
    "        # return res\n",
    "                    \n",
    "\n",
    "        # next_rain = [-1]*len(rains)\n",
    "        # rain_dict = {}\n",
    "        # for i in reversed(range(len(rains))):\n",
    "        #     if rains[i]:\n",
    "        #         if rains[i] in rain_dict:\n",
    "        #             next_rain[i] = rain_dict[rains[i]]\n",
    "        #         rain_dict[rains[i]] = i\n",
    "        # danger = []\n",
    "        # ret = []\n",
    "        # immediate_danger = 0\n",
    "        # for i, lake in enumerate(rains):\n",
    "        #     if lake > 0:\n",
    "        #         if lake == immediate_danger:\n",
    "        #             return []\n",
    "        #         ret.append(-1)\n",
    "        #         if next_rain[i]!=-1:\n",
    "        #             heapq.heappush(danger, (next_rain[i], lake))\n",
    "        #             immediate_danger = danger[0][1]\n",
    "        #     elif danger:\n",
    "        #         target = heapq.heappop(danger)\n",
    "        #         ret.append(target[1])\n",
    "        #         if danger:\n",
    "        #             immediate_danger = danger[0][1]\n",
    "        #         else:\n",
    "        #             immediate_danger = 0\n",
    "        #     else:\n",
    "        #         ret.append(1)\n",
    "        # return ret\n",
    "\n",
    "        n = len(rains)\n",
    "        next_rain = [-1 for _ in range(n)]\n",
    "        rainy = dict()\n",
    "        for i in range(n - 1, -1, -1) :\n",
    "            if (x := rains[i]) :\n",
    "                next_rain[i] = rainy.get(x, -1)\n",
    "                rainy[x] = i\n",
    "        lakes = []\n",
    "        res = []\n",
    "        # danger = 0\n",
    "        for i, x in enumerate(rains) :\n",
    "            if x :\n",
    "                if lakes and x == lakes[0][1] :\n",
    "                    return []\n",
    "                res.append(-1)\n",
    "                if next_rain[i] != -1 :\n",
    "                    heapq.heappush(lakes, (next_rain[i], x))\n",
    "            elif lakes :\n",
    "                res.append(heapq.heappop(lakes)[1])\n",
    "            else :\n",
    "                res.append(1)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def avoidFlood(self, rains: List[int]) -> List[int]:\n",
    "        ret = [1] * len(rains)\n",
    "        norain = []\n",
    "        pre_rainday = {}\n",
    "        raincount = set()\n",
    "        for i in range(len(rains)):\n",
    "            if rains[i] == 0:\n",
    "                norain.append(i)\n",
    "            else:\n",
    "                ret[i] = -1\n",
    "                if rains[i] in raincount:\n",
    "                    idx = bisect_right(norain, pre_rainday[rains[i]])\n",
    "                    if idx == len(norain):\n",
    "                        return []\n",
    "                    ret[norain[idx]] = rains[i]\n",
    "                    del norain[idx]\n",
    "                raincount.add(rains[i])\n",
    "                pre_rainday[rains[i]] = i\n",
    "            \n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedSet\n",
    "class Solution:\n",
    "    def avoidFlood(self, rains: List[int]) -> List[int]:\n",
    "        ans = [1] * len(rains)\n",
    "        lake_rain = dict() #一个湖泊上次下雨的时候\n",
    "        st = SortedSet() #保存可以抽水的日子\n",
    "\n",
    "        for i in range(len(rains)):\n",
    "            if (rains[i] == 0):\n",
    "                st.add(i)\n",
    "            else:\n",
    "                ans[i] = -1\n",
    "                if (rains[i] in lake_rain):\n",
    "                    #已经满了，试着找一天抽水\n",
    "                    idx = st.bisect(lake_rain[rains[i]])\n",
    "                    if (idx < len(st)):\n",
    "                        ans[st[idx]] = rains[i]\n",
    "                        st.discard(st[idx])\n",
    "                    else:\n",
    "                        return []\n",
    "                lake_rain[rains[i]] = i\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def avoidFlood(self, rains: List[int]) -> List[int]:\n",
    "        cs=[]\n",
    "        pool={}\n",
    "        index={}\n",
    "        for i in range(len(rains)):\n",
    "            pool[rains[i]]=0\n",
    "            index[rains[i]]=0\n",
    "        ans=[-1]*len(rains)\n",
    "        for i in range(len(rains)):\n",
    "            if rains[i]==0:\n",
    "                cs.append(i)\n",
    "            else :\n",
    "                pool[rains[i]]+=1\n",
    "                if pool[rains[i]]==1:\n",
    "                    index[rains[i]]=i\n",
    "                elif pool[rains[i]]==2:\n",
    "                    if len(cs)==0 or cs[0]>i or cs[-1]<index[rains[i]]:\n",
    "                        return []\n",
    "                    else :\n",
    "                        j=0\n",
    "                        while cs[j]<index[rains[i]]:\n",
    "                            j+=1\n",
    "                        pool[rains[i]]=1\n",
    "                        index[rains[i]]=i\n",
    "                        ans[cs[j]]=rains[i]\n",
    "                        cs.remove(cs[j])\n",
    "        for i in range(len(cs)):\n",
    "            ans[cs[i]]=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def avoidFlood(self, rains: List[int]) -> List[int]:\n",
    "        n = len(rains)\n",
    "        ne = [n+1]*n\n",
    "        ans = [-1]*n\n",
    "        dic = {}\n",
    "        for i in range(n):\n",
    "            if rains[i] in dic:\n",
    "                ne[dic[rains[i]]] = i\n",
    "            dic[rains[i]] = i\n",
    "        h = []\n",
    "        s = set()\n",
    "        for i in range(n):\n",
    "            # print(i, rains[i], h, s)\n",
    "            if rains[i]!=0:\n",
    "                if rains[i] in s:\n",
    "                    return []\n",
    "                s.add(rains[i])\n",
    "                heapq.heappush(h, (ne[i], rains[i]))\n",
    "            else:\n",
    "                if h:\n",
    "                    _, t = heapq.heappop(h) \n",
    "                    s.remove(t)\n",
    "                else:\n",
    "                    t = 1\n",
    "                ans[i] = t\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def avoidFlood(self, rains: List[int]) -> List[int]:\n",
    "        processDict = {}\n",
    "        processDict[0] = []\n",
    "\n",
    "        result = []\n",
    "        for key, val in enumerate(rains):\n",
    "            if val not in processDict:\n",
    "                processDict[val] = [key]\n",
    "                result.append(-1)\n",
    "                continue\n",
    "\n",
    "            if val == 0:\n",
    "                result.append(1)\n",
    "                processDict[val].append(key)\n",
    "                continue\n",
    "\n",
    "\n",
    "            if len(processDict[val]) + 1 > 1:\n",
    "                for i in processDict[0]:\n",
    "                    if i > processDict[val][0]:\n",
    "                        result[i] = val\n",
    "                        processDict[0].remove(i)\n",
    "                        processDict[val] = [key]\n",
    "                        break\n",
    "                if processDict[val] != [key]:\n",
    "                    return []\n",
    "                \n",
    "\n",
    "            result.append(-1)\n",
    "\n",
    "        return result        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def avoidFlood(self, rains: List[int]) -> List[int]: \n",
    "        xx=dict()\n",
    "        length=len(rains)\n",
    "        for i in range(length):\n",
    "            if(rains[i] in xx):\n",
    "                xx[rains[i]].append(i)\n",
    "            else:\n",
    "                xx[rains[i]]=[i]\n",
    "        pool=set()\n",
    "        length=len(rains)\n",
    "        ans=[]\n",
    "        j=0\n",
    "        i=0\n",
    "        # for i in range(len(rains)):\n",
    "        while(i<length):\n",
    "            if(rains[i]!=0):\n",
    "                ans.append(-1)\n",
    "                if(rains[i] in pool):\n",
    "                    return []\n",
    "                else:\n",
    "                    if(len(xx[rains[i]])>1):\n",
    "                        pool.add(rains[i])\n",
    "                i+=1\n",
    "            else:\n",
    "                zero_len=0\n",
    "                while(i<length and rains[i]==0):\n",
    "                    zero_len+=1\n",
    "                    i+=1\n",
    "                if(len(pool)==0):\n",
    "                    ans.extend([1]*zero_len)\n",
    "                else:\n",
    "                    j=i\n",
    "                    while(j<length and zero_len>0):\n",
    "                        if(rains[j] in pool):\n",
    "                            ans.append(rains[j])\n",
    "                            pool.remove(rains[j])\n",
    "                            zero_len-=1\n",
    "                        j+=1\n",
    "                    if(zero_len!=0):\n",
    "                        ans.extend([1]*zero_len)\n",
    "                    # free_latest_id=length\n",
    "                    # for one_pool in pool:\n",
    "                    #     tmp=xx[one_pool] # 一个湖泊的下雨顺序\n",
    "                    #     for k in tmp:\n",
    "                    #         if(k>i):\n",
    "                    #             if(k<free_latest_id):\n",
    "                    #                 free_latest_id=k\n",
    "                    #             break\n",
    "                    # if(free_latest_id==length):ans.append(1)\n",
    "                    # else:\n",
    "                    #     ans.append(rains[free_latest_id])\n",
    "                    #     pool.remove(rains[free_latest_id])\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def avoidFlood(self, rains: List[int]) -> List[int]:\n",
    "        dic = dict()\n",
    "        n = len(rains)\n",
    "        nxt_pos = [n] * n\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            r = rains[i]\n",
    "            if r in dic:\n",
    "                nxt_pos[i] = dic[r]\n",
    "            dic[r] = i\n",
    "        ans = [-1] * n\n",
    "        h = []\n",
    "        fulled = set()\n",
    "        for i in range(n):\n",
    "            r = rains[i]\n",
    "            if r:\n",
    "                if r in fulled:\n",
    "                    return []\n",
    "                fulled.add(r)\n",
    "                heappush(h, (nxt_pos[i], r))\n",
    "            else:\n",
    "                if h:\n",
    "                    r = heappop(h)[1]\n",
    "                    fulled.remove(r)\n",
    "                    ans[i] = r\n",
    "                else:\n",
    "                    ans[i] = 1\n",
    "        return ans\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def avoidFlood(self, rains: List[int]) -> List[int]:\n",
    "        pull_list = []\n",
    "        rain_map = defaultdict(list)\n",
    "        ans = []\n",
    "        random_lake = 0\n",
    "        for index, rain in enumerate(rains):\n",
    "            if rain > 0:\n",
    "                random_lake = rain\n",
    "                ans.append(-1)\n",
    "                rain_map[rain].append(index)\n",
    "                if len(rain_map[rain]) > 1:\n",
    "                    pull = rain_map[rain].pop(0)\n",
    "                    pull_index = bisect.bisect(pull_list, pull)\n",
    "                    # print(rain_map, pull_list, pull_index)\n",
    "                    if pull_index == len(pull_list): # 抽不了\n",
    "                        return []\n",
    "                    else:\n",
    "                        ans[pull_list[pull_index]] = rain\n",
    "                        pull_list.remove(pull_list[pull_index])\n",
    "                        # print(pull_list)\n",
    "                        # print()\n",
    "            else:\n",
    "                ans.append(0)\n",
    "                pull_list.append(index)\n",
    "        for i in range(len(ans)):\n",
    "            if ans[i] == 0:\n",
    "                ans[i] = random_lake\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left\n",
    "from collections import defaultdict\n",
    "from heapq import heappop, heappush\n",
    "\n",
    "class Solution:\n",
    "    def avoidFlood(self, rains: List[int]) -> List[int]:\n",
    "        rain_days = defaultdict(list)\n",
    "        for i, r in enumerate(rains):\n",
    "            if r > 0:\n",
    "                rain_days[r].append(i)\n",
    "        \n",
    "        ans = [-1] * len(rains)\n",
    "        need_running = []\n",
    "        for i, r in enumerate(rains):\n",
    "            if r > 0:\n",
    "                index = bisect_left(rain_days[r], i)\n",
    "                if index >= len(rain_days[r]) - 1:\n",
    "                    continue\n",
    "                heappush(need_running, (rain_days[r][index + 1], r))\n",
    "            else:\n",
    "                if need_running:\n",
    "                    next_index, r = heappop(need_running)\n",
    "                    if next_index > i:\n",
    "                        ans[i] = r\n",
    "                    else:\n",
    "                        return []\n",
    "                else:\n",
    "                    ans[i] = 1\n",
    "        if need_running:\n",
    "            return []\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def avoidFlood(self, rains: List[int]) -> List[int]:\n",
    "        '''\n",
    "        采用贪心算法, 每次抽的时候, 抽最近要下雨的那个湖\n",
    "        首先倒着遍历数组, 求到下一次下雨的时间\n",
    "        每次下雨用一个堆来排序下次最近要下雨的湖\n",
    "        一次pop堆即可\n",
    "        '''\n",
    "        lst = {}\n",
    "        N = len(rains)\n",
    "        lstIndex = [inf] * N\n",
    "        for i in range(N-1, -1, -1):\n",
    "            if rains[i] in lst:\n",
    "                lstIndex[i] = lst[rains[i]]\n",
    "            \n",
    "            lst[rains[i]] = i\n",
    "        maxlake = max(rains) + 1000\n",
    "        \n",
    "        ans = []\n",
    "        lakes = set()\n",
    "        h = []\n",
    "        for i in range(N):\n",
    "            if rains[i] > 0:\n",
    "                if rains[i] in lakes:\n",
    "                    return []\n",
    "                ans.append(-1)\n",
    "                lakes.add(rains[i])\n",
    "                heappush(h, (lstIndex[i] - i, rains[i]))\n",
    "            else:\n",
    "                if h:\n",
    "                    days, lake = heappop(h)\n",
    "                    lakes.remove(lake)\n",
    "                    ans.append(lake)\n",
    "                else:\n",
    "                    ans.append(maxlake)\n",
    "        return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def avoidFlood(self, rains: List[int]) -> List[int]:\n",
    "        h = []\n",
    "        ans = [-1]*len(rains)\n",
    "        d = {}\n",
    "        next_rain = {}\n",
    "        for i in range(len(rains)-1, -1, -1):\n",
    "            if rains[i] in d:\n",
    "                next_rain[i] = d[rains[i]]\n",
    "            d[rains[i]] = i\n",
    "                \n",
    "        s = set()\n",
    "        for i, r in enumerate(rains):\n",
    "            if r:\n",
    "                if r in s:\n",
    "                    return []\n",
    "                if i in next_rain:\n",
    "                    heapq.heappush(h, [next_rain[i], r])\n",
    "                s.add(r)\n",
    "            else:\n",
    "                if h:\n",
    "                    _, r = heapq.heappop(h)\n",
    "                    ans[i] = r\n",
    "                    s.remove(r)\n",
    "                else:\n",
    "                    ans[i] = 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def avoidFlood(self, rains: List[int]) -> List[int]:\n",
    "        pos = defaultdict(list)\n",
    "        for i, r in enumerate(rains):\n",
    "            if r != 0:\n",
    "                pos[r].append(i)\n",
    "\n",
    "        ans = [-1] * len(rains)\n",
    "        full = set()\n",
    "        next_rain = []\n",
    "        for j, r in enumerate(rains):\n",
    "            if r in full:\n",
    "                return []\n",
    "            elif r != 0:\n",
    "                full.add(r)\n",
    "                if len(pos[r]) > 1:\n",
    "                    heapq.heappush(next_rain, (pos[r].pop(1), r))\n",
    "            else:\n",
    "                if len(next_rain) > 0:\n",
    "                    _, a = heapq.heappop(next_rain)\n",
    "                    full.remove(a)\n",
    "                    ans[j] = a\n",
    "                else:\n",
    "                    ans[j] = 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def avoidFlood(self, rains: List[int]) -> List[int]:\n",
    "        n = len(rains)\n",
    "        day_count = collections.defaultdict(list)\n",
    "        full = set()\n",
    "        res = []\n",
    "        dry_days = []\n",
    "\n",
    "        for i, lake in enumerate(rains):\n",
    "            if lake:\n",
    "                day_count[lake].append(i)\n",
    "        \n",
    "        for i, lake in enumerate(rains):\n",
    "            if lake:\n",
    "                if lake in full:\n",
    "                    return []\n",
    "                \n",
    "                res.append(-1)\n",
    "                full.add(lake)\n",
    "\n",
    "                day_count[lake].pop(0)\n",
    "                if day_count[lake]:\n",
    "                    heapq.heappush(dry_days, day_count[lake][0])\n",
    "            else:\n",
    "                if dry_days:\n",
    "                    next_rain = heapq.heappop(dry_days)\n",
    "                    res.append(rains[next_rain])\n",
    "                    full.remove(rains[next_rain])\n",
    "                else:\n",
    "                    res.append(1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def avoidFlood(self, rains: List[int]) -> List[int]:\n",
    "        n = len(rains)\n",
    "        ret = [-1] * n\n",
    "        poolid = {}\n",
    "        poolidcnt = 0\n",
    "        poolprv = Counter() # idx+1\n",
    "        s = SortedList()\n",
    "        for i,c in enumerate(rains):\n",
    "            if c == 0:\n",
    "                s.add(i)\n",
    "                continue\n",
    "            if c not in poolid:\n",
    "                poolid[c] = poolidcnt\n",
    "                poolidcnt += 1\n",
    "            pid = poolid[c]\n",
    "            # print(i,c,pid)\n",
    "            if poolprv[pid]:\n",
    "                idx = s.bisect_left(poolprv[pid])\n",
    "                if idx == len(s):\n",
    "                    return []\n",
    "                ret[s[idx]] = c\n",
    "                s.pop(idx)\n",
    "            poolprv[pid] = i+1\n",
    "                \n",
    "\n",
    "        for i in s:\n",
    "            ret[i] = 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def avoidFlood(self, rains: List[int]) -> List[int]:\n",
    "        pool_rain_days = {}\n",
    "        for i in range(len(rains)):\n",
    "            if rains[i] != 0:\n",
    "                pool_rain_days[rains[i]] = pool_rain_days.get(rains[i], []) + [i]\n",
    "\n",
    "        ans = []\n",
    "        not_empty = []\n",
    "        not_empty_set = set()\n",
    "\n",
    "        for i in range(len(rains)):\n",
    "            if rains[i] > 0:\n",
    "                if rains[i] in not_empty_set:\n",
    "                    return []\n",
    "                else:\n",
    "                    ans.append(-1)\n",
    "                    if pool_rain_days[rains[i]]:\n",
    "                        pool_rain_days[rains[i]].pop(0)\n",
    "                    heapq.heappush(not_empty, (pool_rain_days[rains[i]].pop(0) if pool_rain_days[rains[i]] else float('inf'), rains[i]))\n",
    "                    not_empty_set.add(rains[i])\n",
    "            else:\n",
    "                if not_empty:\n",
    "                    _, pool = heapq.heappop(not_empty)\n",
    "                    ans.append((pool))\n",
    "                    not_empty_set.remove(pool)\n",
    "                else:\n",
    "                    ans.append(1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def avoidFlood(self, rains: List[int]) -> List[int]:\n",
    "        d=defaultdict(list)\n",
    "        for i,v in enumerate(rains):\n",
    "            d[v].append(i)\n",
    "        n=len(rains)\n",
    "        ans=[-1]*n\n",
    "        lakefull=set()\n",
    "        again=[]\n",
    "        for i in range(n):\n",
    "            if rains[i]>0:\n",
    "                if rains[i] in lakefull:\n",
    "                    return []\n",
    "                else:\n",
    "                    lakefull.add(rains[i])\n",
    "                    if len(d[rains[i]])>1:\n",
    "                        heapq.heappush(again,d[rains[i]][1])\n",
    "                        d[rains[i]]=d[rains[i]][1:]\n",
    "            else:\n",
    "                if again:\n",
    "                    recent=heapq.heappop(again)\n",
    "                    ans[i]=rains[recent]\n",
    "                    lakefull.remove(rains[recent])\n",
    "                else:\n",
    "                    ans[i]=1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def avoidFlood(self, rains: List[int]) -> List[int]:\n",
    "        # n = len(rains)\n",
    "        # res = [1 for _ in range(n)]\n",
    "        # sunny = SortedList()\n",
    "        # rainy = dict()\n",
    "        # for i, x in enumerate(rains) :\n",
    "        #     if x :\n",
    "        #         res[i] = -1\n",
    "        #         if x in rainy :\n",
    "        #             idx = sunny.bisect_right(rainy[x])\n",
    "        #             if idx == len(sunny) :\n",
    "        #                 return []\n",
    "        #             res[sunny[idx]] = x\n",
    "        #             sunny.remove(sunny[idx])\n",
    "        #         rainy[x] = i\n",
    "        #     else :\n",
    "        #         sunny.add(i)\n",
    "\n",
    "        # return res\n",
    "\n",
    "\n",
    "        # n = len(rains)\n",
    "        # res = [1 for _ in range(n)]\n",
    "        # rainy = dict()\n",
    "        # pa = list(range(n + 1))\n",
    "        # def find(x):\n",
    "        #     if pa[x] != x:\n",
    "        #         pa[x] = find(pa[x])\n",
    "        #     return pa[x]\n",
    "        # # def union(x):\n",
    "        # #     pa[find(x)] = find(x + 1)\n",
    "        \n",
    "        # for i, x in enumerate(rains) :\n",
    "        #     if x :\n",
    "        #         res[i] = -1\n",
    "        #         if x in rainy :\n",
    "        #             idx = find(rainy[x])\n",
    "        #             if idx == i :\n",
    "        #                 return []\n",
    "        #             res[idx] = x\n",
    "        #             pa[idx] = idx + 1\n",
    "        #             # union(idx)\n",
    "        #         rainy[x] = i\n",
    "        #         pa[i] = i + 1\n",
    "        #         # union(i)\n",
    "        # return res\n",
    "                    \n",
    "\n",
    "        # next_rain = [-1]*len(rains)\n",
    "        # rain_dict = {}\n",
    "        # for i in reversed(range(len(rains))):\n",
    "        #     if rains[i]:\n",
    "        #         if rains[i] in rain_dict:\n",
    "        #             next_rain[i] = rain_dict[rains[i]]\n",
    "        #         rain_dict[rains[i]] = i\n",
    "        # danger = []\n",
    "        # ret = []\n",
    "        # immediate_danger = 0\n",
    "        # for i, lake in enumerate(rains):\n",
    "        #     if lake > 0:\n",
    "        #         if lake == immediate_danger:\n",
    "        #             return []\n",
    "        #         ret.append(-1)\n",
    "        #         if next_rain[i]!=-1:\n",
    "        #             heapq.heappush(danger, (next_rain[i], lake))\n",
    "        #             immediate_danger = danger[0][1]\n",
    "        #     elif danger:\n",
    "        #         target = heapq.heappop(danger)\n",
    "        #         ret.append(target[1])\n",
    "        #         if danger:\n",
    "        #             immediate_danger = danger[0][1]\n",
    "        #         else:\n",
    "        #             immediate_danger = 0\n",
    "        #     else:\n",
    "        #         ret.append(1)\n",
    "        # return ret\n",
    "\n",
    "        n = len(rains)\n",
    "        next_rain = [-1 for _ in range(n)]\n",
    "        rainy = dict()\n",
    "        for i, x in reversed(list(enumerate(rains))) :\n",
    "            if x :\n",
    "                next_rain[i] = rainy.get(x, -1)\n",
    "                rainy[x] = i\n",
    "        lakes = []\n",
    "        res = []\n",
    "        # danger = 0\n",
    "        for i, x in enumerate(rains) :\n",
    "            if x :\n",
    "                if lakes and x == lakes[0][1] :\n",
    "                    return []\n",
    "                res.append(-1)\n",
    "                if next_rain[i] != -1 :\n",
    "                    heapq.heappush(lakes, (next_rain[i], x))\n",
    "            elif lakes :\n",
    "                res.append(heapq.heappop(lakes)[1])\n",
    "            else :\n",
    "                res.append(1)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def avoidFlood(self, rains: List[int]) -> List[int]:\n",
    "        # n = len(rains)\n",
    "        # res = [1 for _ in range(n)]\n",
    "        # sunny = SortedList()\n",
    "        # rainy = dict()\n",
    "        # for i, x in enumerate(rains) :\n",
    "        #     if x :\n",
    "        #         res[i] = -1\n",
    "        #         if x in rainy :\n",
    "        #             idx = sunny.bisect_right(rainy[x])\n",
    "        #             if idx == len(sunny) :\n",
    "        #                 return []\n",
    "        #             res[sunny[idx]] = x\n",
    "        #             sunny.remove(sunny[idx])\n",
    "        #         rainy[x] = i\n",
    "        #     else :\n",
    "        #         sunny.add(i)\n",
    "\n",
    "        # return res\n",
    "\n",
    "\n",
    "        # n = len(rains)\n",
    "        # res = [1 for _ in range(n)]\n",
    "        # rainy = dict()\n",
    "        # pa = list(range(n + 1))\n",
    "        # def find(x):\n",
    "        #     if pa[x] != x:\n",
    "        #         pa[x] = find(pa[x])\n",
    "        #     return pa[x]\n",
    "        # # def union(x):\n",
    "        # #     pa[find(x)] = find(x + 1)\n",
    "        \n",
    "        # for i, x in enumerate(rains) :\n",
    "        #     if x :\n",
    "        #         res[i] = -1\n",
    "        #         if x in rainy :\n",
    "        #             idx = find(rainy[x])\n",
    "        #             if idx == i :\n",
    "        #                 return []\n",
    "        #             res[idx] = x\n",
    "        #             pa[idx] = idx + 1\n",
    "        #             # union(idx)\n",
    "        #         rainy[x] = i\n",
    "        #         pa[i] = i + 1\n",
    "        #         # union(i)\n",
    "        # return res\n",
    "                    \n",
    "\n",
    "        # next_rain = [-1]*len(rains)\n",
    "        # rain_dict = {}\n",
    "        # for i in reversed(range(len(rains))):\n",
    "        #     if rains[i]:\n",
    "        #         if rains[i] in rain_dict:\n",
    "        #             next_rain[i] = rain_dict[rains[i]]\n",
    "        #         rain_dict[rains[i]] = i\n",
    "        # danger = []\n",
    "        # ret = []\n",
    "        # immediate_danger = 0\n",
    "        # for i, lake in enumerate(rains):\n",
    "        #     if lake > 0:\n",
    "        #         if lake == immediate_danger:\n",
    "        #             return []\n",
    "        #         ret.append(-1)\n",
    "        #         if next_rain[i]!=-1:\n",
    "        #             heapq.heappush(danger, (next_rain[i], lake))\n",
    "        #             immediate_danger = danger[0][1]\n",
    "        #     elif danger:\n",
    "        #         target = heapq.heappop(danger)\n",
    "        #         ret.append(target[1])\n",
    "        #         if danger:\n",
    "        #             immediate_danger = danger[0][1]\n",
    "        #         else:\n",
    "        #             immediate_danger = 0\n",
    "        #     else:\n",
    "        #         ret.append(1)\n",
    "        # return ret\n",
    "\n",
    "        n = len(rains)\n",
    "        next_rain = [-1 for _ in range(n)]\n",
    "        rainy = dict()\n",
    "        for i, x in reversed(list(enumerate(rains))) :\n",
    "            if x :\n",
    "                next_rain[i] = rainy.get(x, -1)\n",
    "                rainy[x] = i\n",
    "        lakes = []\n",
    "        res = []\n",
    "        # danger = 0\n",
    "        for i, x in enumerate(rains) :\n",
    "            if x :\n",
    "                if lakes and x == lakes[0][1] :\n",
    "                    return []\n",
    "                res.append(-1)\n",
    "                if next_rain[i] != -1 :\n",
    "                    heapq.heappush(lakes, (next_rain[i], x))\n",
    "            elif lakes :\n",
    "                res.append(heapq.heappop(lakes)[1])\n",
    "            else :\n",
    "                res.append(1)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def avoidFlood(self, rains: List[int]) -> List[int]:\n",
    "        data_indices = defaultdict(list)\n",
    "        full_lakes = set()\n",
    "        rain_avail_pq = []\n",
    "        n = len(rains)\n",
    "        ans = [-1] * n\n",
    "        for i,r in enumerate(rains):\n",
    "            data_indices[r].append(i)\n",
    "\n",
    "        def find_next(lake, target):\n",
    "            arr = data_indices[lake]\n",
    "            left, right = 0, len(arr) - 1\n",
    "            ans = -1\n",
    "            while left <= right:\n",
    "                middle = (left + right) // 2\n",
    "                if arr[middle] > target:\n",
    "                    ans = arr[middle]\n",
    "                    right = middle - 1\n",
    "                else:\n",
    "                    left = middle + 1\n",
    "            return ans\n",
    "\n",
    "        for i, r in enumerate(rains):\n",
    "            if r != 0:\n",
    "                if r in full_lakes:\n",
    "                    return []\n",
    "                else:\n",
    "                    full_lakes.add(r)\n",
    "                    next_index = find_next(r, i)\n",
    "                    heappush(rain_avail_pq, (next_index if next_index != -1 else n, r))\n",
    "            else:\n",
    "                if rain_avail_pq:\n",
    "                    index, lake  = heappop(rain_avail_pq)\n",
    "                    full_lakes.discard(lake)\n",
    "                    ans[i] = lake\n",
    "                else:\n",
    "                    ans[i] = 1\n",
    "        return ans\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def avoidFlood(self, rains: List[int]) -> List[int]:\n",
    "        # n = len(rains)\n",
    "        # res = [1 for _ in range(n)]\n",
    "        # sunny = SortedList()\n",
    "        # rainy = dict()\n",
    "        # for i, x in enumerate(rains) :\n",
    "        #     if x :\n",
    "        #         res[i] = -1\n",
    "        #         if x in rainy :\n",
    "        #             idx = sunny.bisect_right(rainy[x])\n",
    "        #             if idx == len(sunny) :\n",
    "        #                 return []\n",
    "        #             res[sunny[idx]] = x\n",
    "        #             sunny.remove(sunny[idx])\n",
    "        #         rainy[x] = i\n",
    "        #     else :\n",
    "        #         sunny.add(i)\n",
    "\n",
    "        # return res\n",
    "\n",
    "\n",
    "        # n = len(rains)\n",
    "        # res = [1 for _ in range(n)]\n",
    "        # rainy = dict()\n",
    "        # pa = list(range(n + 1))\n",
    "        # def find(x):\n",
    "        #     if pa[x] != x:\n",
    "        #         pa[x] = find(pa[x])\n",
    "        #     return pa[x]\n",
    "        # # def union(x):\n",
    "        # #     pa[find(x)] = find(x + 1)\n",
    "        \n",
    "        # for i, x in enumerate(rains) :\n",
    "        #     if x :\n",
    "        #         res[i] = -1\n",
    "        #         if x in rainy :\n",
    "        #             idx = find(rainy[x])\n",
    "        #             if idx == i :\n",
    "        #                 return []\n",
    "        #             res[idx] = x\n",
    "        #             pa[idx] = idx + 1\n",
    "        #             # union(idx)\n",
    "        #         rainy[x] = i\n",
    "        #         pa[i] = i + 1\n",
    "        #         # union(i)\n",
    "        # return res\n",
    "                    \n",
    "\n",
    "        # next_rain = [-1]*len(rains)\n",
    "        # rain_dict = {}\n",
    "        # for i in reversed(range(len(rains))):\n",
    "        #     if rains[i]:\n",
    "        #         if rains[i] in rain_dict:\n",
    "        #             next_rain[i] = rain_dict[rains[i]]\n",
    "        #         rain_dict[rains[i]] = i\n",
    "        # danger = []\n",
    "        # ret = []\n",
    "        # immediate_danger = 0\n",
    "        # for i, lake in enumerate(rains):\n",
    "        #     if lake > 0:\n",
    "        #         if lake == immediate_danger:\n",
    "        #             return []\n",
    "        #         ret.append(-1)\n",
    "        #         if next_rain[i]!=-1:\n",
    "        #             heapq.heappush(danger, (next_rain[i], lake))\n",
    "        #             immediate_danger = danger[0][1]\n",
    "        #     elif danger:\n",
    "        #         target = heapq.heappop(danger)\n",
    "        #         ret.append(target[1])\n",
    "        #         if danger:\n",
    "        #             immediate_danger = danger[0][1]\n",
    "        #         else:\n",
    "        #             immediate_danger = 0\n",
    "        #     else:\n",
    "        #         ret.append(1)\n",
    "        # return ret\n",
    "\n",
    "        n = len(rains)\n",
    "        next_rain = [-1 for _ in range(n)]\n",
    "        rainy = dict()\n",
    "        for i, x in reversed(list(enumerate(rains))) :\n",
    "            if x :\n",
    "                next_rain[i] = rainy.get(x, -1)\n",
    "                rainy[x] = i\n",
    "        lakes = []\n",
    "        res = []\n",
    "        # danger = 0\n",
    "        for i, x in enumerate(rains) :\n",
    "            if x :\n",
    "                if lakes and x == lakes[0][1] :\n",
    "                    return []\n",
    "                res.append(-1)\n",
    "                if next_rain[i] != -1 :\n",
    "                    heapq.heappush(lakes, (next_rain[i], x))\n",
    "            elif lakes :\n",
    "                res.append(heapq.heappop(lakes)[1])\n",
    "            else :\n",
    "                res.append(1)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "import heapq\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def avoidFlood(self, rains: List[int]) -> List[int]:\n",
    "        status = collections.defaultdict(bool)  # 保存湖泊状态\n",
    "        hp_index = collections.defaultdict(list)    # 保存每个湖泊的下雨索引\n",
    "        deque = []  # 优先级队列\n",
    "        heapq.heapify(deque)\n",
    "        ans = []\n",
    "        for index, rain in enumerate(rains):    # 初始化湖泊的下雨索引\n",
    "            hp_index[rain].append(index)\n",
    "\n",
    "        for index, rain in enumerate(rains):\n",
    "            if rain > 0:    # 如果下雨，则先判断当前下雨的湖泊没有满，则修改当前湖泊的状态。如果满了，则直接返回空数组表示泛红\n",
    "                if rain not in status.keys() or status[rain] == False:\n",
    "                    status[rain] = True\n",
    "                else:\n",
    "                    return []\n",
    "                # 获取当前湖泊下一次下雨的日期。\n",
    "                indexes = hp_index[rain]\n",
    "                if indexes:\n",
    "                    indexes = indexes[1:]   # 因为hp_index中已经存储了当前湖泊的所有下雨日期，第一个取值必定是当前下雨的日期。\n",
    "                    hp_index[rain] = indexes\n",
    "                # 上面已经删除了第一个日期，接下来的日期就是下一次下雨的日期。此时如果存在下一次下雨的日期，则将下一次下雨的日期和湖泊编号添加到优先级队列中\n",
    "                if indexes:\n",
    "                    next_index = indexes[0]\n",
    "                    heapq.heappush(deque, (next_index, rain))\n",
    "                ans.append(-1)\n",
    "            else:\n",
    "                # 如果不下雨，且优先级队列中存在值，根据贪心思想，则优先从其中抽取最近要下雨的湖泊。\n",
    "                if len(deque):\n",
    "                    index, rain = heapq.heappop(deque)\n",
    "                    status[rain] = False\n",
    "                    ans.append(rain)\n",
    "                # 如果不下雨，且不存在需要抽取的湖泊，则默认抽取第一个湖泊。否则这里会只能通过部分测试用例\n",
    "                else:\n",
    "                    ans.append(1)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef avoidFlood(self, rains):\n",
    "\t\tlast = {}\n",
    "\t\tpool = []\n",
    "\t\tans = [-1] * len(rains)\n",
    "\t\tfor i, lake in enumerate(rains):\n",
    "\t\t\tif lake == 0:\n",
    "\t\t\t\tans[i] = 1\n",
    "\t\t\t\tpool.append([i, 0])\n",
    "\t\t\telse:\n",
    "\t\t\t\tif lake in last:\n",
    "\t\t\t\t\tpool.append([last[lake], lake])\n",
    "\t\t\t\tlast[lake] = i\n",
    "\t\tstack = []\n",
    "\t\tfor i, lake in pool[::-1]:\n",
    "\t\t\tif lake == 0:\n",
    "\t\t\t\tif stack:\n",
    "\t\t\t\t\tif -stack[0][0] > i:\n",
    "\t\t\t\t\t\treturn []\n",
    "\t\t\t\t\tans[i] = heapq.heappop(stack)[1]\n",
    "\t\t\telse:\n",
    "\t\t\t\theapq.heappush(stack, [-i, lake])\n",
    "\t\tif stack:\n",
    "\t\t\treturn []\n",
    "\t\treturn ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def avoidFlood(self, rains):\n",
    "        ans = []\n",
    "        mem = {}\n",
    "        for i in range(len(rains) - 1, -1, -1):\n",
    "            ri = rains[i]\n",
    "            if ri == 0:\n",
    "                continue\n",
    "            if ri not in mem:\n",
    "                mem[ri] = [len(rains)]\n",
    "            mem[ri].append(i)\n",
    "        \n",
    "        pool_full = set([])\n",
    "        h = []\n",
    "\n",
    "        for i in range(len(rains)):\n",
    "            ri = rains[i]\n",
    "            if ri > 0:\n",
    "                if ri in pool_full:\n",
    "                    return []\n",
    "                mem[ri].pop()\n",
    "                heapq.heappush(h, (mem[ri][-1], ri))\n",
    "                ans.append(-1)\n",
    "                pool_full.add(ri)\n",
    "            else:\n",
    "                if len(pool_full) == 0:\n",
    "                    ans.append(123)\n",
    "                else:\n",
    "                    _, rj = heapq.heappop(h)\n",
    "                    ans.append(rj)\n",
    "                    pool_full.remove(rj)\n",
    "        return ans \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def avoidFlood(self, rains: List[int]) -> List[int]:\n",
    "        rain_dict = defaultdict(list)\n",
    "        rain_dict_idx = defaultdict(int)\n",
    "        \n",
    "        res = []\n",
    "        for i, lake in enumerate(rains):\n",
    "            rain_dict[lake].append(i)\n",
    "            rain_dict_idx[lake] = 0\n",
    "        \n",
    "        pq = []\n",
    "        full_lakes = set()\n",
    "        for lake in rains:\n",
    "            # print(rain_dict, rain_dict_idx)\n",
    "            if lake != 0:\n",
    "                if lake in full_lakes:\n",
    "                    return []\n",
    "                \n",
    "                full_lakes.add(lake)\n",
    "                rain_dict_idx[lake] += 1\n",
    "                if rain_dict_idx[lake] < len(rain_dict[lake]):\n",
    "                    heappush(pq, (rain_dict[lake][rain_dict_idx[lake]], lake))\n",
    "                \n",
    "                res.append(-1)\n",
    "            else:\n",
    "                if pq:\n",
    "                    _, lake = heappop(pq)\n",
    "                    res.append(lake)\n",
    "                    full_lakes.remove(lake)\n",
    "                else:\n",
    "                    res.append(10000)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def avoidFlood(self, rains: List[int]) -> List[int]:\n",
    "        n = len(rains)\n",
    "        # 答案\n",
    "        ans = [-1] * n\n",
    "        # cnt = Counter(rains)\n",
    "        # 可以排水的 \n",
    "        index = []\n",
    "        # 已经满的\n",
    "        visited = set()\n",
    "\n",
    "        # 获取一个随机排水名额\n",
    "        xx = iter(set(rains))\n",
    "        x = next(xx)\n",
    "        if x == 0:\n",
    "            x = next(xx)\n",
    "        \n",
    "\n",
    "        # 存位置\n",
    "        dic = defaultdict(list)\n",
    "        for i in range(n-1, -1, -1):\n",
    "            dic[rains[i]].append(i)\n",
    "\n",
    "        for i, r in enumerate(rains):\n",
    "            # 会下雨\n",
    "            if r > 0:\n",
    "                dic[r].pop()\n",
    "                # 已经满了\n",
    "                if r in visited:\n",
    "                    return []\n",
    "                # 没有满, 加满\n",
    "                else:\n",
    "                    visited.add(r)\n",
    "                    if dic[r]:\n",
    "                        j = dic[r][-1]\n",
    "                        heappush(index, (j, r))\n",
    "            # 可以排水\n",
    "            else:\n",
    "                # 排什么水\n",
    "                if index:\n",
    "                    j, rr = heappop(index)\n",
    "                    ans[i] = rr\n",
    "                    visited.remove(rr)\n",
    "                else:\n",
    "                    ans[i] = x\n",
    "            \n",
    "        return ans\n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import *\n",
    "\n",
    "class Solution:\n",
    "    def avoidFlood(self, rains: List[int]) -> List[int]:\n",
    "        dic, heap, res, already = {}, [], [], set()\n",
    "        for i in range(len(rains)):\n",
    "            if rains[i]:\n",
    "                dic.setdefault(rains[i], []).append(i)\n",
    "        for x in dic:\n",
    "            dic[x].append(float(\"inf\"))\n",
    "            dic[x].reverse()\n",
    "        for x in rains:\n",
    "            if x:\n",
    "                if x in already:\n",
    "                    return []\n",
    "                already.add(x)\n",
    "                dic[x].pop()\n",
    "                heappush(heap, [dic[x].pop(), x])\n",
    "                res.append(-1)\n",
    "            else:\n",
    "                if heap:\n",
    "                    pres = heappop(heap)\n",
    "                    dic[pres[1]].append(pres[0])\n",
    "                    already.remove(pres[1])\n",
    "                    res.append(pres[1])\n",
    "                else:\n",
    "                    res.append(1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def avoidFlood(self, rains: List[int]) -> List[int]:\n",
    "        pos = defaultdict(list)\n",
    "        idx = {}\n",
    "        for i, r in enumerate(rains):\n",
    "            idx[r] = 0\n",
    "            pos[r].append(i)\n",
    "        print(pos)\n",
    "        ans = []\n",
    "        h = []\n",
    "        seen = set()\n",
    "        for i, r in enumerate(rains):\n",
    "            if r > 0:\n",
    "                ans.append(-1)\n",
    "                if r in seen:\n",
    "                    return []\n",
    "                seen.add(r)\n",
    "                next_i = idx[r] + 1\n",
    "                idx[r] += 1\n",
    "                if next_i < len(pos[r]):\n",
    "                    heappush(h, (pos[r][next_i], r))\n",
    "            else:\n",
    "                if len(h) > 0:\n",
    "                    (p, pool) = heappop(h)\n",
    "                    seen.remove(pool)\n",
    "                    ans.append(pool)\n",
    "                else:\n",
    "                    ans.append(1)\n",
    "        \n",
    "        return ans\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self,val=0,pre=None,next = None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "        self.pre = pre\n",
    "\n",
    "class Solution:\n",
    "    def avoidFlood(self, rains: List[int]) -> List[int]:\n",
    "        head = Node(-1)\n",
    "        tail = Node(-1)\n",
    "        head.next = tail\n",
    "        tail.pre = head\n",
    "        n = len(rains)\n",
    "        ans = [1 for _ in range(n)]\n",
    "        full = {}\n",
    "        for i,j in enumerate(rains):\n",
    "            if j > 0:\n",
    "                if j in full:\n",
    "                    cur = head\n",
    "                    while cur:\n",
    "                        if cur.val > full[j]:\n",
    "                            ans[cur.val] = j\n",
    "                            preNode = cur.pre\n",
    "                            nextNode = cur.next\n",
    "                            preNode.next,nextNode.pre = nextNode,preNode\n",
    "                            break\n",
    "                        cur = cur.next\n",
    "                    else:\n",
    "                        return []\n",
    "                ans[i] = -1\n",
    "                full[j] = i\n",
    "            else:\n",
    "                if not full:continue\n",
    "                node = Node(i)\n",
    "                lastNode = tail.pre\n",
    "                lastNode.next,node.pre = node,lastNode\n",
    "                node.next = tail\n",
    "                tail.pre = node\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # n = len(rains)\n",
    "        # record = []\n",
    "        # # full保存所有已经满水的湖泊以及他最后一次满的时刻是多少\n",
    "        # full = {}\n",
    "        # ans = [1]*n\n",
    "        # for i,j in enumerate(rains):\n",
    "        #     # 下雨了\n",
    "        #     if j>0:\n",
    "        #         # 该湖泊是满的\n",
    "        #         if j in full:\n",
    "        #             tmp = []\n",
    "        #             while record:\n",
    "        #                 idx = heappop(record)\n",
    "        #                 if idx > full[j]:\n",
    "        #                     ans[idx] = j\n",
    "        #                     for each in tmp:\n",
    "        #                         heappush(record,each)\n",
    "        #                     break\n",
    "        #                 tmp.append(idx)\n",
    "        #             else:\n",
    "        #                 return []\n",
    "        #         full[j] = i\n",
    "        #         ans[i] = -1\n",
    "        #     else:\n",
    "        #         if full:\n",
    "        #             heappush(record,i)\n",
    "        #         else:\n",
    "        #             record.clear()\n",
    "        # return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self,val=0,pre=None,next = None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "        self.pre = pre\n",
    "\n",
    "class Solution:\n",
    "    def avoidFlood(self, rains: List[int]) -> List[int]:\n",
    "        head = Node(-1)\n",
    "        tail = Node(-1)\n",
    "        head.next = tail\n",
    "        tail.pre = head\n",
    "        n = len(rains)\n",
    "        ans = [1 for _ in range(n)]\n",
    "        full = {}\n",
    "        for i,j in enumerate(rains):\n",
    "            if j > 0:\n",
    "                if j in full:\n",
    "                    cur = head\n",
    "                    while cur:\n",
    "                        if cur.val > full[j]:\n",
    "                            ans[cur.val] = j\n",
    "                            preNode = cur.pre\n",
    "                            nextNode = cur.next\n",
    "                            preNode.next,nextNode.pre = nextNode,preNode\n",
    "                            break\n",
    "                        cur = cur.next\n",
    "                    else:\n",
    "                        return []\n",
    "                ans[i] = -1\n",
    "                full[j] = i\n",
    "            else:\n",
    "                node = Node(i)\n",
    "                lastNode = tail.pre\n",
    "                lastNode.next,node.pre = node,lastNode\n",
    "                node.next = tail\n",
    "                tail.pre = node\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        n = len(rains)\n",
    "        record = []\n",
    "        # full保存所有已经满水的湖泊以及他最后一次满的时刻是多少\n",
    "        full = {}\n",
    "        ans = [1]*n\n",
    "        for i,j in enumerate(rains):\n",
    "            # 下雨了\n",
    "            if j>0:\n",
    "                # 该湖泊是满的\n",
    "                if j in full:\n",
    "                    tmp = []\n",
    "                    while record:\n",
    "                        idx = heappop(record)\n",
    "                        if idx > full[j]:\n",
    "                            ans[idx] = j\n",
    "                            for each in tmp:\n",
    "                                heappush(record,each)\n",
    "                            break\n",
    "                        tmp.append(idx)\n",
    "                    else:\n",
    "                        return []\n",
    "                full[j] = i\n",
    "                ans[i] = -1\n",
    "            else:\n",
    "                if full:\n",
    "                    heappush(record,i)\n",
    "                else:\n",
    "                    record.clear()\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 重点是理解题意\n",
    "    # 必须在两次降水之间找到清空湖泊的机会\n",
    "    # O(N ^ 2)\n",
    "    def avoidFlood(self, rains: List[int]) -> List[int]:\n",
    "\n",
    "        N = len(rains)\n",
    "        d = collections.defaultdict(int)\n",
    "        ans = [-1] * N \n",
    "\n",
    "        for i in range(N):\n",
    "            if not rains[i]:\n",
    "                ans[i] = 0\n",
    "        \n",
    "        for i in range(N):\n",
    "            if rains[i]:\n",
    "                if d[rains[i]]:\n",
    "                    flag = True \n",
    "                    for j in range(d[rains[i]], i):\n",
    "                        if not ans[j]:\n",
    "                            ans[j] = rains[i]\n",
    "                            flag = False \n",
    "                            break\n",
    "                    if flag:\n",
    "                        return []\n",
    "                d[rains[i]] = i + 1\n",
    "            \n",
    "        c = 0\n",
    "        for i in range(1, 10 ** 5 + 1):\n",
    "            if i not in set(rains):\n",
    "                c = i\n",
    "                break\n",
    "    \n",
    "        for i in range(len(ans)):\n",
    "            if not ans[i]:\n",
    "                ans[i] = c\n",
    "            \n",
    "        return ans \n",
    "            \n",
    "    def avoidFlood(self, rains: List[int]) -> List[int]:\n",
    "\n",
    "        N = len(rains)\n",
    "        d = collections.defaultdict(int)\n",
    "        ans = [-1] * N \n",
    "        tmp = []\n",
    "\n",
    "        for i in range(N):\n",
    "            if not rains[i]:\n",
    "                ans[i] = 0\n",
    "                tmp.append(i)\n",
    "                \n",
    "        for i in range(N):\n",
    "            if rains[i]:\n",
    "                if d[rains[i]]:\n",
    "                    left = bisect.bisect(tmp, d[rains[i]] - 1)\n",
    "                    right = bisect.bisect(tmp, i) - 1\n",
    "                    if left <= right:\n",
    "                        ans[tmp[left]] = rains[i]\n",
    "                        tmp.pop(left)\n",
    "                    else:\n",
    "                        return []\n",
    "                d[rains[i]] = i + 1\n",
    "            \n",
    "        c = list(set(i for i in range(1, 10 ** 5)) - set(rains)).pop()\n",
    "        for i in range(len(ans)):\n",
    "            if not ans[i]:\n",
    "                ans[i] = c\n",
    "            \n",
    "        return ans \n",
    "\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "from enum import Enum\n",
    "class Color(Enum):\n",
    "    Red = 1\n",
    "    Black = 2\n",
    "\n",
    "\n",
    "T = TypeVar(\"T\")\n",
    "\n",
    "\n",
    "class RBTreeNode(Generic[T]):\n",
    "    def __init__(self, key: T, color: Color = Color.Black, size: int = 0,\n",
    "                 p: Optional[\"RBTreeNode\"] = None, left: Optional[\"RBTreeNode\"] = None, right: Optional[\"RBTreeNode\"] = None):\n",
    "        self.key = key\n",
    "        self.color = color\n",
    "        # x.size = x.left.size + x.right.size + 1\n",
    "        self.size = size  # 树的大小.\n",
    "        self.p: \"RBTreeNode\" = p\n",
    "        self.left: \"RBTreeNode\" = left\n",
    "        self.right: \"RBTreeNode\" = right\n",
    "\n",
    "\n",
    "\"\"\"红黑树特性\n",
    "1. 特殊的二叉搜索树(BST). 保证没有一条路径会比其他路径长2倍, 因此是平衡的.\n",
    "2. 若某节点无子节点/父节点, 则对应指针指向nil(用nil节点代替None, 使得代码结构更清晰)\n",
    "    空树: root=nil. \n",
    "3. 根节点, nil为黑色. 若某节点为红, 则取两节点为黑. \n",
    "    对于每个节点, 该节点到nil的路径上, 具有相同黑色节点. \n",
    "\"\"\"\n",
    "\n",
    "\n",
    "class RBTree(Generic[T]):\n",
    "    \"\"\"\n",
    "    Ref: 算法导论\n",
    "    note: 可重复. 类似于c++的multiset\n",
    "    \"\"\"\n",
    "\n",
    "    def __init__(self):\n",
    "        # 空树\n",
    "        nil = RBTreeNode(0, Color.Black)\n",
    "        self.root = nil\n",
    "        self.nil = nil\n",
    "\n",
    "    def getitem(self, i: int) -> RBTreeNode:\n",
    "        return self._getitem(self.root, i)\n",
    "\n",
    "    def _getitem(self, tn: RBTreeNode, i: int) -> RBTreeNode:\n",
    "        \"\"\"返回x为根的子树的第i小关键字(从0开始)(即SortedList中sl[i])的节点\"\"\"\n",
    "        idx = tn.left.size  # 当前节点的索引\n",
    "        if i == idx:\n",
    "            return tn\n",
    "        elif i < idx:\n",
    "            return self._getitem(tn.left, i)\n",
    "        else:\n",
    "            return self._getitem(tn.right, i - idx - 1)\n",
    "\n",
    "    def bisect_left(self, x: T) -> int:\n",
    "        \"\"\"获取SortedList中x值的lower bound索引.\"\"\"\n",
    "        tn = self.root\n",
    "        res = 0\n",
    "        while tn is not self.nil:\n",
    "            if x <= tn.key:\n",
    "                tn = tn.left\n",
    "            else:\n",
    "                res += tn.left.size + 1\n",
    "                tn = tn.right\n",
    "        return res\n",
    "\n",
    "    def bisect_right(self, x: T) -> int:\n",
    "        \"\"\"获取SortedList中x值的upper bound索引.\"\"\"\n",
    "        tn = self.root\n",
    "        res = 0\n",
    "        while tn is not self.nil:\n",
    "            if x < tn.key:\n",
    "                tn = tn.left\n",
    "            else:\n",
    "                res += tn.left.size + 1\n",
    "                tn = tn.right\n",
    "        return res\n",
    "\n",
    "    def search(self, x: T) -> RBTreeNode:\n",
    "        \"\"\"搜索key=k的tn\"\"\"\n",
    "        tn = self.root\n",
    "        while tn is not self.nil and x != tn.key:\n",
    "            if x < tn.key:\n",
    "                tn = tn.left\n",
    "            else:\n",
    "                tn = tn.right\n",
    "        return tn\n",
    "\n",
    "    def _left_rotate(self, x: RBTreeNode) -> None:\n",
    "        \"\"\"左旋. x为旋转根\"\"\"\n",
    "        y = x.right\n",
    "        assert y is not self.nil  # 假设\n",
    "        x.right = y.left\n",
    "        if y.left is not self.nil:\n",
    "            y.left.p = x\n",
    "        y.p = x.p\n",
    "        if x.p is self.nil:\n",
    "            self.root = y\n",
    "        elif x is x.p.left:\n",
    "            x.p.left = y\n",
    "        else:\n",
    "            x.p.right = y\n",
    "        y.left = x\n",
    "        x.p = y\n",
    "        y.size = x.size\n",
    "        x.size = x.left.size + x.right.size + 1\n",
    "\n",
    "    def _right_rotate(self, y: RBTreeNode) -> None:\n",
    "        \"\"\"右旋, y为旋转根\"\"\"\n",
    "        x = y.left\n",
    "        assert x is not self.nil\n",
    "        y.left = x.right\n",
    "        if x.right is not self.nil:\n",
    "            x.right.p = y\n",
    "        x.p = y.p\n",
    "        if y.p is self.nil:\n",
    "            self.root = x\n",
    "        elif y is y.p.left:\n",
    "            y.p.left = x\n",
    "        else:\n",
    "            y.p.right = x\n",
    "        x.right = y\n",
    "        y.p = x\n",
    "        x.size = y.size\n",
    "        y.size = y.left.size + y.right.size + 1\n",
    "\n",
    "    def insert(self, z: RBTreeNode) -> None:\n",
    "        \"\"\"插入z节点\"\"\"\n",
    "        y = self.nil\n",
    "        x = self.root\n",
    "        # 找位置.\n",
    "        while x is not self.nil:\n",
    "            y = x\n",
    "            x.size += 1\n",
    "            if z.key < x.key:\n",
    "                x = x.left\n",
    "            else:\n",
    "                x = x.right\n",
    "        # 插入\n",
    "        z.p = y\n",
    "        if y is self.nil:\n",
    "            self.root = z\n",
    "        elif z.key < y.key:\n",
    "            y.left = z\n",
    "        else:\n",
    "            y.right = z\n",
    "        z.left = self.nil\n",
    "        z.right = self.nil\n",
    "        z.color = Color.Red  # 置为红, z可能违背红黑性质\n",
    "        z.size = 1\n",
    "        self._rb_insert_fixup(z)\n",
    "\n",
    "    def _rb_insert_fixup(self, z: RBTreeNode) -> None:\n",
    "        # z: 可能违背红黑性质的节点\n",
    "        while z.p.color is Color.Red:\n",
    "            if z.p is z.p.p.left:\n",
    "                y = z.p.p.right\n",
    "                if y.color is Color.Red:\n",
    "                    z.p.color = Color.Black\n",
    "                    y.color = Color.Black\n",
    "                    z.p.p.color = Color.Red\n",
    "                    z = z.p.p\n",
    "                elif z is z.p.right:\n",
    "                    z = z.p\n",
    "                    self._left_rotate(z)\n",
    "                else:\n",
    "                    z.p.color = Color.Black\n",
    "                    z.p.p.color = Color.Red\n",
    "                    self._right_rotate(z.p.p)\n",
    "            else:\n",
    "                y = z.p.p.left\n",
    "                if y.color is Color.Red:\n",
    "                    z.p.color = Color.Black\n",
    "                    y.color = Color.Black\n",
    "                    z.p.p.color = Color.Red\n",
    "                    z = z.p.p\n",
    "                elif z is z.p.left:\n",
    "                    z = z.p\n",
    "                    self._right_rotate(z)\n",
    "                else:\n",
    "                    z.p.color = Color.Black\n",
    "                    z.p.p.color = Color.Red\n",
    "                    self._left_rotate(z.p.p)\n",
    "        self.root.color = Color.Black\n",
    "\n",
    "    def _rb_transplant(self, u: RBTreeNode, v: RBTreeNode) -> None:\n",
    "        # 用v替代u, 删除节点时使用\n",
    "        if u.p is self.nil:\n",
    "            self.root = v\n",
    "        elif u is u.p.left:\n",
    "            u.p.left = v\n",
    "        else:\n",
    "            u.p.right = v\n",
    "        v.p = u.p\n",
    "\n",
    "    def _tree_minimum(self, x: RBTreeNode) -> RBTreeNode:\n",
    "        \"\"\"找二叉搜索树中的最小值(一直往左找)\"\"\"\n",
    "        while x.left is not self.nil:\n",
    "            x = x.left\n",
    "        return x\n",
    "\n",
    "    def delete(self, z: RBTreeNode) -> None:\n",
    "        \"\"\"删除z\"\"\"\n",
    "        # y: 在树中删除的节点或者移至树内的节点\n",
    "        # x: 移到y的原始位置上\n",
    "        y = z\n",
    "        y_original_color = y.color\n",
    "        if z.left is self.nil:\n",
    "            x = z.right\n",
    "            self._rb_transplant(z, z.right)\n",
    "        elif z.right is self.nil:\n",
    "            x = z.left\n",
    "            self._rb_transplant(z, z.left)\n",
    "        else:\n",
    "            y = self._tree_minimum(z.right)\n",
    "            y_original_color = y.color\n",
    "            x = y.right\n",
    "            if y.p is z:\n",
    "                x.p = y\n",
    "            else:\n",
    "                self._rb_transplant(y, y.right)\n",
    "                y.right = z.right\n",
    "                y.right.p = y\n",
    "            self._rb_transplant(z, y)\n",
    "            y.left = z.left\n",
    "            y.left.p = y\n",
    "            y.color = z.color\n",
    "            y.size = z.size\n",
    "        p = x.p\n",
    "        while p is not self.nil:\n",
    "            p.size -= 1\n",
    "            p = p.p\n",
    "        #\n",
    "        if y_original_color is Color.Black:\n",
    "            self._rb_delete_fixup(x)  # 删了一个黑\n",
    "\n",
    "    def _rb_delete_fixup(self, x: RBTreeNode) -> None:\n",
    "        while x is not self.root and x.color is Color.Black:\n",
    "            if x is x.p.left:\n",
    "                w = x.p.right\n",
    "                if w.color is Color.Red:\n",
    "                    w.color = Color.Black\n",
    "                    x.p.color = Color.Red\n",
    "                    self._left_rotate(x.p)\n",
    "                    w = x.p.right\n",
    "                if w.left.color is Color.Black and w.right.color is Color.Black:\n",
    "                    w.color = Color.Red\n",
    "                    x = x.p\n",
    "                elif w.right.color is Color.Black:\n",
    "                    w.left.color = Color.Black\n",
    "                    w.color = Color.Red\n",
    "                    self._right_rotate(w)\n",
    "                    w = x.p.right\n",
    "                else:\n",
    "                    w.color = x.p.color\n",
    "                    x.p.color = Color.Black\n",
    "                    w.right.color = Color.Black\n",
    "                    self._left_rotate(x.p)\n",
    "                    x = self.root\n",
    "            else:\n",
    "                w = x.p.left\n",
    "                if w.color is Color.Red:\n",
    "                    w.color = Color.Black\n",
    "                    x.p.color = Color.Red\n",
    "                    self._right_rotate(x.p)\n",
    "                    w = x.p.left\n",
    "                if w.right.color is Color.Black and w.left.color is Color.Black:\n",
    "                    w.color = Color.Red\n",
    "                    x = x.p\n",
    "                elif w.left.color is Color.Black:\n",
    "                    w.right.color = Color.Black\n",
    "                    w.color = Color.Red\n",
    "                    self._left_rotate(w)\n",
    "                    w = x.p.left  # 保证一致性\n",
    "                else:\n",
    "                    w.color = x.p.color\n",
    "                    x.p.color = Color.Black\n",
    "                    w.left.color = Color.Black\n",
    "                    self._right_rotate(x.p)\n",
    "                    x = self.root\n",
    "        x.color = Color.Black\n",
    "\n",
    "    def _inorder_traversal(self, tn: RBTreeNode, res: List[T]) -> None:\n",
    "        if tn is self.nil:\n",
    "            return\n",
    "        self._inorder_traversal(tn.left, res)\n",
    "        res.append(tn.key)\n",
    "        self._inorder_traversal(tn.right, res)\n",
    "\n",
    "    def __repr__(self) -> str:\n",
    "        \"\"\"中序遍历\"\"\"\n",
    "        res = []\n",
    "        self._inorder_traversal(self.root, res)\n",
    "        return repr(res)\n",
    "\n",
    "\n",
    "class RBSortedList(Generic[T]):\n",
    "    def __init__(self, nums: Optional[List[T]] = None) -> None:\n",
    "        if nums is None:\n",
    "            nums = []\n",
    "        self.rbt = RBTree()\n",
    "        for x in nums:\n",
    "            self.add(x)\n",
    "\n",
    "    def add(self, x: T) -> None:\n",
    "        self.rbt.insert(RBTreeNode(x))\n",
    "\n",
    "    def remove(self, x: T) -> None:\n",
    "        tn = self.rbt.search(x)\n",
    "        assert tn is not self.rbt.nil\n",
    "        self.rbt.delete(tn)\n",
    "\n",
    "    def bisect_left(self, x: T) -> int:\n",
    "        return self.rbt.bisect_left(x)\n",
    "\n",
    "    def bisect_right(self, x: T) -> int:\n",
    "        return self.rbt.bisect_right(x)\n",
    "\n",
    "    def pop(self, i: int) -> T:\n",
    "        tn = self.rbt.getitem(i)\n",
    "        res = tn.key\n",
    "        self.rbt.delete(tn)\n",
    "        return res\n",
    "\n",
    "    def __len__(self) -> int:\n",
    "        return self.rbt.root.size\n",
    "\n",
    "    def __getitem__(self, i: int) -> T:\n",
    "        if i < 0:\n",
    "            i = i + len(self)\n",
    "        if i >= len(self):\n",
    "            raise IndexError\n",
    "        return self.rbt.getitem(i).key\n",
    "\n",
    "    def __repr__(self) -> str:\n",
    "        return f\"{self.__class__.__name__}({self.rbt!r})\"\n",
    "\n",
    "class SimpleSortedList(Generic[T]):\n",
    "    \"\"\"使用二分法搜索实现有序的list.\n",
    "        or 使用库: sortedcontainers\n",
    "    \"\"\"\n",
    "\n",
    "    def __init__(self, nums: Optional[List[T]] = None) -> None:\n",
    "        if nums is None:\n",
    "            nums = []\n",
    "        self.sl: List[T] = nums\n",
    "        self.sl.sort()\n",
    "\n",
    "    def add(self, x: T) -> None:\n",
    "        idx = self.bisect_right(x)\n",
    "        self.sl.insert(idx, x)\n",
    "\n",
    "    def remove(self, x: T) -> None:\n",
    "        # 只删一个. 同sortedcontainers.SortedList\n",
    "        idx = self.bisect_right(x) - 1\n",
    "        if self.sl[idx] != x:\n",
    "            raise ValueError(\"x not find\")\n",
    "        self.sl.pop(idx)\n",
    "\n",
    "    def bisect_left(self, x: T) -> int:\n",
    "        \"\"\"return: [0..len(self)]\"\"\"\n",
    "        return bisect_left(self.sl, x)\n",
    "\n",
    "    def bisect_right(self, x: T) -> int:\n",
    "        \"\"\"return: [0..len(self)]\"\"\"\n",
    "        return bisect_right(self.sl, x)\n",
    "\n",
    "    def pop(self, i: int) -> T:\n",
    "        return self.sl.pop(i)\n",
    "\n",
    "    def __len__(self) -> int:\n",
    "        return len(self.sl)\n",
    "\n",
    "    def __getitem__(self, idx: int) -> T:\n",
    "        return self.sl[idx]\n",
    "\n",
    "    def __repr__(self) -> str:\n",
    "        return f\"{self.__class__.__name__}({self.sl})\"\n",
    "\n",
    "class Solution:\n",
    "    def avoidFlood(self, rains: List[int]) -> List[int]:\n",
    "        \"\"\"将抽的天数存起来. \n",
    "        -: lake_date: 对于每一个湖. 最近的下雨的日期. \n",
    "            sum_set: 晴天的池, 存日期. \n",
    "        若遇到某天下雨, 但是湖以及满了, 则查看上一次下雨和这次下雨之间由于空闲的晴天, 在那一天倒水. \n",
    "            若有则清除晴天. 没有则失败.        \n",
    "        \"\"\"\n",
    "        n = len(rains)\n",
    "        res = [-1] * n\n",
    "        lake_date = DefaultDict[int, int]()\n",
    "        sum_date = RBSortedList()\n",
    "        for date in range(n):\n",
    "            lake_idx = rains[date]\n",
    "            if lake_idx == 0:\n",
    "                sum_date.add(date)\n",
    "            else:\n",
    "                if lake_idx not in lake_date:\n",
    "                    lake_date[lake_idx] = date\n",
    "                else:\n",
    "                    last_date = lake_date[lake_idx]\n",
    "                    i = sum_date.bisect_left(last_date)\n",
    "                    if i < len(sum_date):  # 存在\n",
    "                        lake_date[lake_idx] = date\n",
    "                        d = sum_date[i]\n",
    "                        res[d] = lake_idx\n",
    "                        sum_date.pop(i)\n",
    "                    else:\n",
    "                        return []\n",
    "        # 剩下的sum_set, 随意抽光一个湖, 这里取第一个湖\n",
    "        for date in sum_date:\n",
    "            res[date] = 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def avoidFlood(self, rains: List[int]) -> List[int]:\n",
    "        N = len(rains)\n",
    "        # 计算当天下雨之后第一个可以抽水的日期\n",
    "        day = list(range(N+1))\n",
    "        last = N\n",
    "        for i in range(N-1, -1, -1):\n",
    "            if rains[i] == 0:\n",
    "                last = i\n",
    "            else:\n",
    "                day[i] = last\n",
    "        #print(day)\n",
    "        # 并查集，查找第一个可以抽水的日期\n",
    "        def find(d):\n",
    "            if day[d] != d:\n",
    "                day[d] = find(day[d])\n",
    "            return day[d]\n",
    "\n",
    "        idx = dict()\n",
    "        ans = [1] * N\n",
    "        for i, r in enumerate(rains):\n",
    "            if r == 0:\n",
    "                continue\n",
    "            ans[i] = -1\n",
    "            if r in idx:\n",
    "                d = find(idx[r])\n",
    "                # 在当天以前无法抽水\n",
    "                if d >= i:\n",
    "                    return []\n",
    "                ans[d] = r                \n",
    "                # 指向下一个可能抽水的日期\n",
    "                day[d] = d + 1\n",
    "            idx[r] = i\n",
    "        #print(day)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def avoidFlood(self, rains: List[int]) -> List[int]:\n",
    "        import heapq\n",
    "        proff = dict()\n",
    "        curr = dict()\n",
    "        for idx in rains:\n",
    "            proff[idx] = []\n",
    "            curr[idx] = 0\n",
    "        for ii in range(len(rains)):\n",
    "            proff[rains[ii]].append(ii)\n",
    "        res = [-1]*(len(rains))\n",
    "        mydeq = []\n",
    "        for ii in range(len(rains)):\n",
    "            if rains[ii]==0:\n",
    "                if len(mydeq):\n",
    "                    idx = mydeq[0]\n",
    "                    heapq.heappop(mydeq)\n",
    "                    curr[idx[1]] = 0\n",
    "                    res[ii] = idx[1]\n",
    "                else:\n",
    "                    res[ii ] = 1\n",
    "            else:\n",
    "                idx = rains[ii]\n",
    "                if curr[idx]:\n",
    "                    return []\n",
    "                l = 0\n",
    "                r = len(proff[idx])-1\n",
    "                while l<=r:\n",
    "                    mid =( (r-l)>>1)+l\n",
    "                    if proff[idx][mid]<=ii:\n",
    "                        l = mid+1\n",
    "                    else:\n",
    "                        r = mid-1\n",
    "                curr[idx] = 1\n",
    "                heapq.heappush(mydeq, (len(rains) if l==len(proff[idx]) else proff[idx][l],idx))\n",
    "                \n",
    "\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def avoidFlood(self, rains: List[int]) -> List[int]:\n",
    "        count_dict = {}\n",
    "        #计数\n",
    "        for i in range(len(rains)):\n",
    "            if rains[i]!=0:\n",
    "                if rains[i] not in count_dict:\n",
    "                    count_dict[rains[i]] = [[i],0]\n",
    "                else:\n",
    "                    count_dict[rains[i]][0] += [i]\n",
    "        ans = []\n",
    "        record ={}\n",
    "        kwag = {}\n",
    "        sl = SortedList()\n",
    "        for i in range(len(rains)):\n",
    "            if rains[i]!=0:\n",
    "                if rains[i] not in record:\n",
    "                    record[rains[i]] = 1\n",
    "                    count_dict[rains[i]][1] += 1\n",
    "                    kwag[rains[i]] = count_dict[rains[i]][0][count_dict[rains[i]][1]] if count_dict[rains[i]][1] < len(count_dict[rains[i]][0]) else 100001\n",
    "                else:\n",
    "                    record[rains[i]] += 1\n",
    "                    count_dict[rains[i]][1] += 1\n",
    "                    kwag[rains[i]] = count_dict[rains[i]][0][count_dict[rains[i]][1]] if count_dict[rains[i]][1] < len(count_dict[rains[i]][0]) else 100001\n",
    "                \n",
    "                if record[rains[i]] == 2:\n",
    "                    return []\n",
    "                sl.add(kwag[rains[i]])\n",
    "                ans.append(-1)\n",
    "            else:\n",
    "                #找到离当前最近的下雨日，且在record中出现\n",
    "                min_idx = sl[0] if len(sl) > 0 else 100001\n",
    "                if min_idx == 100001:\n",
    "                    ans.append(1)\n",
    "                else :\n",
    "                    record[rains[min_idx]] -= 1\n",
    "                    sl.remove(min_idx)\n",
    "                    ans.append(rains[min_idx])\n",
    "                \n",
    "        for i in record:\n",
    "            if record[i] >= 2:\n",
    "                return []\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def avoidFlood(self, rains: List[int]) -> List[int]:\n",
    "\n",
    "        bbbb=set(rains)\n",
    "        if len(bbbb)==len(rains) :return [-1]*len(rains)\n",
    "        dp = [0] * len(rains)\n",
    "        raindays = {}   # 日期：下雨的水池号\n",
    "        csds = []       #可以抽水的日期\n",
    "        dic1 = {}       # 水池：【下雨日】\n",
    "        lookup = set()  # 是否下过雨\n",
    "        for i in range(len(rains)):\n",
    "            if rains[i] > 0:\n",
    "                raindays[i] = rains[i]\n",
    "                dic1.setdefault(rains[i], []).append(i)\n",
    "            if rains[i] == 0: csds.append(i)\n",
    "        a = list(raindays.items())\n",
    "        print(a, csds,dic1)\n",
    "        \n",
    "        for k,v in raindays.items():\n",
    "            if v not in lookup:\n",
    "                dp[k] = -1\n",
    "            else:\n",
    "                if not csds: return []\n",
    "                fw=dic1[v]\n",
    "                for m in range(len(csds)):\n",
    "                    #print(min1,csds[m],a[i][0])\n",
    "                    if fw[0] < csds[m] < fw[1]:\n",
    "                        dp[csds[m]] = v\n",
    "                        dp[k] = -1\n",
    "                        csds.pop(m)\n",
    "                        dic1[v].pop(0)\n",
    "                        break\n",
    "                if dp[k] == 0: return []\n",
    "            lookup.add(v)\n",
    "        if csds:\n",
    "            for jj in csds:\n",
    "                dp[jj] = 1\n",
    "        return dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def avoidFlood(self, rains: List[int]) -> List[int]:\n",
    "        data_dict = {}\n",
    "        ans = []\n",
    "        time_interval = np.zeros(len(rains))  #记录第I天下雨的湖泊，未来多少天会再次下雨，初始为0\n",
    "        id_interval = np.zeros(len(rains))\n",
    "        '''数据预处理'''\n",
    "        for i in range(len(rains)-1,-1,-1):\n",
    "            now_lake = rains[i]\n",
    "            if(now_lake > 0):\n",
    "                #此前该湖泊没有记录 即当前湖泊未来不会下雨\n",
    "                if(now_lake not in data_dict.keys()):\n",
    "                    #记录当前下雨的天数\n",
    "                    data_dict[now_lake] = i\n",
    "                #此前湖泊有记录，即当前湖泊未来会下雨\n",
    "                else:\n",
    "                    #记录两次下雨的间隔天数\n",
    "                    time_interval[i] = data_dict[now_lake] - i\n",
    "                    id_interval[i] = now_lake\n",
    "                    #更新该湖泊最后一次下雨的天数\n",
    "                    data_dict[now_lake] = i\n",
    "        tasks = [] #优先队列\n",
    "        '''遍历time_interval 并进入优先队列'''\n",
    "        for i in range(len(rains)):\n",
    "            if(rains[i] >0):\n",
    "                ans.append(-1)\n",
    "                #push 当天下雨的湖泊的最近下雨天数及湖泊名字,传入的日期\n",
    "                input_date = i\n",
    "                #只Push未来还会下雨的湖泊time_interval[]\n",
    "                if(time_interval[i] >0):\n",
    "                    heapq.heappush(tasks,(time_interval[i],id_interval[i],input_date))\n",
    "            #不下雨，选择最紧急的抽干\n",
    "            else:\n",
    "                #输出最近要再次下雨的元组（天数，湖泊编号）\n",
    "                if(len(tasks) >0 ):\n",
    "                    get_out = heapq.heappop(tasks)\n",
    "                    #来不及抽取   input_date + time_interval < nowdate ->已经发生了溢出\n",
    "                    if(get_out[0]+get_out[2] < i):\n",
    "                        return []\n",
    "\n",
    "                    ans.append(int(get_out[1]))\n",
    "                else:\n",
    "                    ans.append(1)\n",
    "        #仍有任务未执行，return null\n",
    "        if(len(tasks)>0):\n",
    "            return []\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def avoidFlood(self, rains: List[int]) -> List[int]:\n",
    "        n = len(rains)        \n",
    "        tr = [0] * 4 * n\n",
    "        p = [  1 if not x else 0 for x in rains ]\n",
    "        def build(o:int,l:int,r:int)->None:\n",
    "            if l==r:\n",
    "                tr[o] = p[l]\n",
    "                return\n",
    "            m = (l+r)//2\n",
    "            build(o<<1,l,m)\n",
    "            build(o<<1|1,m+1,r)\n",
    "            tr[o] = tr[o<<1]+tr[o<<1|1]\n",
    "        \n",
    "        def modify(o:int,L:int,R:int,p:int)->None:\n",
    "            if p==L==R:\n",
    "                tr[o]-=1\n",
    "                return\n",
    "            m = (L+R)//2\n",
    "            if p<=m:\n",
    "                modify(o<<1,L,m,p)\n",
    "            else:\n",
    "                modify(o<<1|1,m+1,R,p)\n",
    "            tr[o] = tr[o<<1] + tr[o<<1|1]\n",
    "        \n",
    "        def query(o:int,l:int,r:int,L:int,R:int)->int:\n",
    "            if L<=l and r<=R:\n",
    "                return tr[o]\n",
    "            m = (l+r)//2\n",
    "            if R<=m:\n",
    "                return query(o<<1,l,m,L,R)\n",
    "            if L>m:\n",
    "                return query(o<<1|1,m+1,r,L,R)\n",
    "            return query(o<<1,l,m,L,R)+query(o<<1|1,m+1,r,L,R)\n",
    "\n",
    "        build(1,0,n-1)\n",
    "        m,ans,q = {},[-1] * n,SortedList()\n",
    "        for i,x in enumerate(rains):\n",
    "            if not x:\n",
    "                q.add(i)\n",
    "                continue\n",
    "            if x in m:\n",
    "                j = m[x]\n",
    "                if not query(1,0,n-1,j,i):\n",
    "                    return []\n",
    "                else:\n",
    "                    y =q.bisect_left(j)\n",
    "                    modify(1,0,n-1,q[y])\n",
    "                    ans[q[y]] = x\n",
    "                    q.remove(q[y])\n",
    "            m[x]=i\n",
    "        for i in range(n):\n",
    "            if ans[i]==-1 and not rains[i]:\n",
    "                ans[i]=1\n",
    "        return ans\n",
    "            \n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def avoidFlood(self, rains: List[int]) -> List[int]:\n",
    "        N = len(rains)\n",
    "        lake = dict()\n",
    "        day = defaultdict(set)\n",
    "\n",
    "        ans = [1] * N\n",
    "        head = Node(-1)\n",
    "        for i, r in enumerate(rains):\n",
    "            #print(f\"{i}, {r}\")\n",
    "            if r == 0:\n",
    "                #print(f\"inset: {head.prv.i}->{i}\")\n",
    "                head.prv.insert(i)\n",
    "                continue\n",
    "            ans[i] = -1\n",
    "            if r not in lake:\n",
    "                lake[r] = head.prv\n",
    "                day[head.prv.i].add(r)\n",
    "            else:\n",
    "                p = lake[r]\n",
    "                #print(f\"got point: {p.i}\")\n",
    "                if p.nxt == head:\n",
    "                    return []\n",
    "                else:\n",
    "                    n = p.nxt.dettach()\n",
    "                    ans[n.i] = r\n",
    "                    day[p.i].remove(r)\n",
    "                    #print(f\"use {n.i}\")\n",
    "                    lake[r] = head.prv\n",
    "                    day[head.prv.i].add(r)\n",
    "                    for x in day[n.i]:\n",
    "                        lake[x] = p\n",
    "                        day[p.i].add(x)\n",
    "                    day[n.i].clear()\n",
    "        return ans\n",
    "\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, i, prv=None, nxt=None):\n",
    "        self.i = i\n",
    "        self.prv = prv or self\n",
    "        self.nxt = nxt or self\n",
    "    \n",
    "    def dettach(self):\n",
    "        self.prv.nxt = self.nxt\n",
    "        self.nxt.prv = self.prv\n",
    "        return self\n",
    "    \n",
    "    def insert(self, i):\n",
    "        n = Node(i, prv=self, nxt=self.nxt)\n",
    "        self.nxt.prv = n\n",
    "        self.nxt = n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
